binary search tree java implementation code examples
이 자습서에서는 Java의 이진 검색 트리를 다룹니다. BST 생성, 요소 삽입, 제거 및 검색, Java에서 BST 트래버스 및 구현 방법을 배웁니다.
이진 검색 트리 (이하 BST라고 함)는 이진 트리 유형입니다. 노드 기반 이진 트리로 정의 할 수도 있습니다. BST는 '순서화 된 이진 트리'라고도합니다. BST에서 왼쪽 하위 트리의 모든 노드에는 루트 노드의 값보다 작은 값이 있습니다.
마찬가지로 BST 오른쪽 하위 트리의 모든 노드에는 루트 노드의 값보다 큰 값이 있습니다. 이 노드 순서는 각 하위 트리에 대해서도 참이어야합니다.
=> 독점적 인 Java 교육 자습서 시리즈를 보려면 여기를 방문하십시오.
학습 내용 :
자바의 이진 검색 트리
BST는 중복 노드를 허용하지 않습니다.
아래 다이어그램은 BST 표현을 보여줍니다.
위 그림은 샘플 BST입니다. 20이이 트리의 루트 노드임을 알 수 있습니다. 왼쪽 하위 트리에는 20보다 작은 모든 노드 값이 있습니다. 오른쪽 하위 트리에는 20보다 큰 모든 노드가 있습니다. 위의 트리가 BST 속성을 충족한다고 말할 수 있습니다.
BST 데이터 구조는 항목의 삽입 / 삭제 및 검색과 관련하여 배열 및 연결된 목록과 비교할 때 매우 효율적인 것으로 간주됩니다.
BST는 요소를 검색하는 데 O (log n) 시간이 걸립니다. 요소가 정렬됨에 따라 요소를 검색하는 동안 모든 단계에서 하위 트리의 절반이 삭제됩니다. 검색 할 요소의 대략적인 위치를 쉽게 결정할 수 있기 때문에 가능합니다.
마찬가지로 삽입 및 삭제 작업은 BST에서 더 효율적입니다. 새 요소를 삽입하려는 경우 요소를 삽입 할 하위 트리 (왼쪽 또는 오른쪽)를 대략적으로 알고 있습니다.
이진 검색 트리 (BST) 만들기
요소 배열이 주어지면 BST를 구성해야합니다.
아래와 같이 해보겠습니다.
주어진 배열 : 45, 10, 7, 90, 12, 50, 13, 39, 57
먼저 최상위 요소, 즉 45를 루트 노드로 고려해 보겠습니다. 여기에서 이미 논의 된 속성을 고려하여 BST를 생성합니다.
트리를 생성하기 위해 배열의 각 요소를 루트와 비교합니다. 그런 다음 트리의 적절한 위치에 요소를 배치합니다.
BST의 전체 생성 프로세스는 다음과 같습니다.
이진 검색 트리 작업
BST는 다양한 작업을 지원합니다. 다음 표는 Java에서 BST가 지원하는 메소드를 보여줍니다. 이러한 각 방법을 개별적으로 설명합니다.
| 방법 / 동작 | 기술 |
|---|---|
| 끼워 넣다 | BST 속성을 위반하지 않고 BST에 요소를 추가합니다. |
| 지우다 | BST에서 주어진 노드를 제거합니다. 노드는 루트 노드, 리프가 아닌 노드 또는 리프 노드 일 수 있습니다. |
| 검색 | BST에서 주어진 요소의 위치를 검색합니다. 이 작업은 트리에 지정된 키가 포함되어 있는지 확인합니다. |
BST에 요소 삽입
요소는 항상 BST에서 리프 노드로 삽입됩니다.
다음은 요소를 삽입하는 단계입니다.
- 루트에서 시작하십시오.
- 삽입 할 요소를 루트 노드와 비교하십시오. 루트보다 작 으면 왼쪽 하위 트리를 탐색하거나 오른쪽 하위 트리를 탐색합니다.
- 원하는 하위 트리의 끝까지 하위 트리를 이동합니다. 노드를 적절한 하위 트리에 리프 노드로 삽입합니다.
BST의 삽입 작업에 대한 그림을 보겠습니다.
다음 BST를 고려하고 트리에 요소 2를 삽입하겠습니다.
BST에 대한 삽입 작업은 위에 나와 있습니다. 그림 (1)에서는 BST에 요소 2를 삽입하기 위해 횡단하는 경로를 보여줍니다. 또한 각 노드에서 확인되는 조건도 표시했습니다. 재귀 비교 결과, 그림 (2)와 같이 요소 2가 1의 오른쪽 자식으로 삽입됩니다.
BST에서 검색 작업
요소가 BST에 있는지 검색하려면 다시 루트에서 시작한 다음 검색 할 요소가 루트보다 작거나 큰지 여부에 따라 왼쪽 또는 오른쪽 하위 트리를 탐색합니다.
다음은 우리가 따라야 할 단계입니다.
- 검색 할 요소를 루트 노드와 비교하십시오.
- 키 (검색 할 요소) = 루트이면 루트 노드를 반환합니다.
- Else if 키
- 그렇지 않으면 오른쪽 하위 트리를 통과합니다.
- 키를 찾거나 트리 끝에 도달 할 때까지 하위 트리 요소를 반복적으로 비교합니다.
예를 들어 검색 작업을 설명하겠습니다. 키 = 12를 검색해야합니다.
아래 그림에서는이 요소를 검색하기 위해 따르는 경로를 추적합니다.
위 그림과 같이 먼저 키를 루트와 비교합니다. 키가 더 크기 때문에 오른쪽 하위 트리를 탐색합니다. 오른쪽 하위 트리에서 키를 오른쪽 하위 트리의 첫 번째 노드와 다시 비교합니다.
키가 15보다 작다는 것을 알았습니다. 따라서 노드 15의 왼쪽 하위 트리로 이동합니다. 바로 왼쪽 노드 15는 키와 일치하는 12입니다. 이 시점에서 검색을 중지하고 결과를 반환합니다.
BST에서 요소 제거
BST에서 노드를 삭제하면 아래에서 설명하는 세 가지 가능성이 있습니다.
노드는 리프 노드입니다.
삭제할 노드가 리프 노드이면 자식 노드가 없으므로이 노드를 직접 삭제할 수 있습니다. 이것은 아래 이미지에 나와 있습니다.
위와 같이 노드 (12)는 리프 노드이며 바로 삭제할 수 있습니다.
노드에는 자식이 하나만 있습니다.
자식이 하나있는 노드를 삭제해야 할 때 노드의 자식 값을 복사 한 다음 자식을 삭제합니다.
위의 다이어그램에서 자식 50이 하나있는 노드 90을 삭제하려고합니다. 따라서 50 값을 90으로 바꾼 다음 이제 자식 노드 인 노드 90을 삭제합니다.
노드에 두 개의 자식이 있음
삭제할 노드에 두 개의 자식이 있으면 노드를 노드의 순차 (왼쪽-루트-오른쪽) 후속 노드로 교체하거나 노드의 오른쪽 하위 트리가 비어 있지 않은 경우 오른쪽 하위 트리의 최소 노드라고 간단히 말합니다. 노드를이 최소 노드로 교체하고 노드를 삭제합니다.
위 다이어그램에서 BST의 루트 노드 인 45 번 노드를 삭제하려고합니다. 이 노드의 오른쪽 하위 트리는 비어 있지 않습니다. 그런 다음 오른쪽 하위 트리를 탐색하고 여기서 노드 50이 최소 노드임을 확인합니다. 따라서 45 대신이 값을 바꾼 다음 45를 삭제합니다.
트리를 확인하면 BST의 속성을 충족 함을 알 수 있습니다. 따라서 노드 교체가 정확했습니다.
Java에서 이진 검색 트리 (BST) 구현
Java의 다음 프로그램은 그림에 사용 된 동일한 트리를 예로 사용하여 위의 모든 BST 작업에 대한 데모를 제공합니다.
기술 지원 분석가 인터뷰 질문 및 답변
class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 / 10 90 / / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }산출:
Java의 BST (Binary Search Tree) 순회
트리는 계층 구조이므로 배열과 같은 다른 데이터 구조와 같이 선형으로 이동할 수 없습니다. 모든 유형의 트리는 모든 하위 트리와 노드가 한 번 이상 방문되도록 특별한 방법으로 순회해야합니다.
루트 노드, 왼쪽 하위 트리 및 오른쪽 하위 트리가 트리에서 순회되는 순서에 따라 아래와 같이 특정 순회가 있습니다.
- Inorder Traversal
- 순회 선주문
- 주문 후 순회
위의 모든 순회는 깊이 우선 기법을 사용합니다. 즉, 트리가 깊이 방향으로 순회됩니다.
트리는 또한 순회를 위해 너비 우선 기법을 사용합니다. 이 기술을 사용하는 접근 방식을 “레벨 오더” 순회.
이 섹션에서는 다음 BST를 예로 사용하여 각 순회를 시연합니다.
위 다이어그램에 표시된 BST를 사용하면 위 트리의 레벨 순서 순회는 다음과 같습니다.
레벨 오더 순회 : 10 6 12 4 8
Inorder Traversal
Inorder traversal 접근 방식은 순서대로 BST를 통과했습니다. 왼쪽 하위 트리 => RootNode => 오른쪽 하위 트리 . inorder traversal은 BST 노드의 감소하는 시퀀스를 제공합니다.
InOrder Traversal을위한 알고리즘 InOrder (bstTree)는 아래와 같습니다.
- InOrder (left_subtree)를 사용하여 왼쪽 하위 트리 탐색
- 루트 노드를 방문하십시오.
- InOrder (right_subtree)를 사용하여 오른쪽 하위 트리 탐색
위 트리의 순서 순회는 다음과 같습니다.
4 6 8 10 12
보시다시피, inorder traversal의 결과로 노드의 순서는 감소하는 순서입니다.
순회 선주문
사전 주문 순회에서는 루트를 먼저 방문한 다음 왼쪽 하위 트리와 오른쪽 하위 트리를 방문합니다. 사전 주문 순회는 트리의 복사본을 만듭니다. 또한 접두사 식을 얻기 위해 식 트리에서 사용할 수 있습니다.
PreOrder (bst_tree) 순회 알고리즘은 다음과 같습니다.
- 루트 노드로 이동
- PreOrder (left_subtree)를 사용하여 왼쪽 하위 트리를 탐색합니다.
- PreOrder (right_subtree)를 사용하여 오른쪽 하위 트리를 탐색합니다.
위에 주어진 BST의 선주문 순회는 다음과 같습니다.
10 6 4 8 12
주문 후 순회
postOrder 순회는 다음 순서로 BST를 순회합니다. 왼쪽 하위 트리-> 오른쪽 하위 트리-> 루트 노드 . PostOrder 순회는 트리를 삭제하거나 표현식 트리의 경우 접미사 표현식을 얻는 데 사용됩니다.
postOrder (bst_tree) 순회 알고리즘은 다음과 같습니다.
- postOrder (left_subtree)를 사용하여 왼쪽 하위 트리를 탐색합니다.
- postOrder (right_subtree)를 사용하여 오른쪽 하위 트리를 탐색합니다.
- 루트 노드로 이동
위의 BST 예제에 대한 postOrder 순회는 다음과 같습니다.
4 8 6 12 10
다음으로 Java 구현에서 깊이 우선 기술을 사용하여 이러한 순회를 구현합니다.
//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } } 산출:
자주 묻는 질문
Q # 1) 이진 검색 트리가 필요한 이유는 무엇입니까?
대답 : 이진 검색 기법을 사용하여 배열과 같은 선형 데이터 구조에서 요소를 검색하는 방식, 트리는 계층 구조이므로 트리에서 요소를 찾는 데 사용할 수있는 구조가 필요합니다.
여기에서 그림으로 요소를 효율적으로 검색하는 데 도움이되는 이진 검색 트리가 있습니다.
Q # 2) 이진 검색 트리의 속성은 무엇입니까?
대답 : 이진 트리 범주에 속하는 이진 검색 트리에는 다음과 같은 속성이 있습니다.
- 이진 검색 트리에 저장된 데이터는 고유합니다. 중복 값은 허용되지 않습니다.
- 왼쪽 하위 트리의 노드는 루트 노드보다 작습니다.
- 오른쪽 하위 트리의 노드가 루트 노드보다 큽니다.
Q # 3) 이진 검색 트리의 응용 프로그램은 무엇입니까?
대답 : 이진 검색 트리를 사용하여 수학의 연속 함수를 해결할 수 있습니다. 이진 검색 트리를 사용하면 계층 구조에서 데이터를 검색하는 것이 더 효율적입니다. 모든 단계에서 검색을 절반의 하위 트리로 줄입니다.
Q # 4) 이진 트리와 이진 검색 트리의 차이점은 무엇입니까?
대답: 이진 트리는 부모로 알려진 각 노드가 최대 두 개의 자식을 가질 수있는 계층 적 트리 구조입니다. 이진 검색 트리는 이진 트리의 모든 속성을 충족하며 고유 한 속성도 있습니다.
이진 검색 트리에서 왼쪽 하위 트리에는 루트 노드보다 작거나 같은 노드가 포함되고 오른쪽 하위 트리에는 루트 노드보다 큰 노드가 있습니다.
Q # 5) 이진 검색 트리는 고유합니까?
대답 : 이진 검색 트리는 이진 트리 범주에 속합니다. 중복 값을 허용하지 않으며 모든 요소가 특정 순서에 따라 정렬된다는 점에서 고유합니다.
결론
이진 검색 트리는 이진 트리 범주의 일부이며 주로 계층 적 데이터 검색에 사용됩니다. 또한 일부 수학적 문제를 해결하는 데 사용됩니다.
이 튜토리얼에서 우리는 이진 검색 트리의 구현을 보았습니다. 또한 그림과 함께 BST에서 수행되는 다양한 작업을 보았고 BST에 대한 순회도 살펴 보았습니다.