소개
이 랩에서는 Java 로 이진 탐색 트리 (Binary Search Tree) 를 구현하는 방법을 배웁니다. 이진 탐색 트리는 각 노드의 값이 왼쪽 서브트리의 값보다 크거나 같고 오른쪽 서브트리의 값보다 작거나 같은 이진 트리 자료 구조입니다.
BSTNode 클래스 생성
먼저, 이진 탐색 트리의 노드를 나타내는 Java 클래스를 생성하고 BSTNode라고 부르겠습니다. 이진 탐색 트리의 노드는 값과 두 개의 자식 노드 (왼쪽과 오른쪽) 를 가져야 합니다.
class BSTNode {
int value;
BSTNode leftChild;
BSTNode rightChild;
BSTNode(int val) {
this.value = val;
this.leftChild = null;
this.rightChild = null;
}
}이진 탐색 트리에 요소 삽입
이진 탐색 트리에 요소를 삽입하려면 다음 알고리즘을 따릅니다.
- 새로운 값이 현재 노드 값보다 작으면 왼쪽 자식으로 재귀합니다.
- 새로운 값이 현재 노드 값보다 크면 오른쪽 자식으로 재귀합니다.
- 현재 노드가 null 이면 이 위치에 새로운 값을 추가합니다.
public static BSTNode insert(int value, BSTNode current) {
if (current == null) {
BSTNode newNode = new BSTNode(value);
return newNode;
} else {
if (value < current.value)
current.leftChild = insert(value, current.leftChild);
else
current.rightChild = insert(value, current.rightChild);
}
return current;
}이 메서드를 테스트하려면 이진 탐색 트리를 생성하고 몇 가지 요소를 삽입합니다.
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Print out the tree to verify the insertion
System.out.println("Traversal after insertion: ");
inorderTraversal(root);
}
// Function to traverse the tree inorder
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}출력:
Traversal after insertion:
5 7 9 12 20 21이진 탐색 트리에서 요소 검색
이진 탐색 트리에서 요소를 검색하려면 다음 알고리즘을 따릅니다.
- 현재 노드의 값이 찾으려는 값과 일치하면 true 를 반환합니다.
- 현재 노드의 값이 찾으려는 값보다 크면 왼쪽 자식으로 재귀합니다.
- 현재 노드의 값이 찾으려는 값보다 작으면 오른쪽 자식으로 재귀합니다.
- 현재 노드가 null 이면 false 를 반환합니다.
public static boolean search(int key, BSTNode current) {
if (current == null)
return false;
if (current.value == key)
return true;
else {
if (key < current.value)
return search(key, current.leftChild);
else
return search(key, current.rightChild);
}
}이 메서드를 테스트하려면 몇 가지 요소를 검색합니다.
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Search for elements
System.out.println(search(7, root));
System.out.println(search(9, root));
System.out.println(search(17, root));
}출력:
true
true
false이진 탐색 트리에서 요소 삭제
이진 탐색 트리에서 요소를 삭제하는 것은 노드 유형에 따라 다른 경우를 처리해야 하므로 이전 단계보다 약간 더 복잡합니다.
- 노드에 자식이 없는 경우 (리프 노드), 단순히 제거합니다.
- 노드에 자식이 하나만 있는 경우, 해당 자식으로 대체합니다.
- 노드에 자식이 두 개인 경우, 오른쪽 서브트리에서 최소값 또는 왼쪽 서브트리에서 최대값으로 대체합니다.
public static BSTNode delete(int value, BSTNode current) {
if (current == null)
return current;
if (value < current.value)
current.leftChild = delete(value, current.leftChild);
else if (value > current.value)
current.rightChild = delete(value, current.rightChild);
else if (value == current.value) {
if (current.leftChild != null && current.rightChild != null) {
int min = current.rightChild.value;
BSTNode temp = current.rightChild;
while (temp.leftChild != null) {
min = temp.leftChild.value;
temp = temp.leftChild;
}
current.value = min;
current.rightChild = delete(min, current.rightChild);
} else if (current.leftChild == null)
return current.rightChild;
else if (current.rightChild == null)
return current.leftChild;
}
return current;
}이 메서드를 테스트하려면 일부 노드를 삭제하고 트리를 출력합니다.
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Delete some nodes
root = delete(12, root);
root = delete(20, root);
root = delete(9, root);
// Print the tree to verify the deletion
System.out.println("Traversal after deletion: ");
inorderTraversal(root);
}출력:
Traversal after deletion:
5 7 21이진 탐색 트리 순회
이진 탐색 트리를 다양한 방식으로 순회할 수 있습니다.
- 중위 순회 (Left-Root-Right)
- 전위 순회 (Root-Left-Right)
- 후위 순회 (Left-Right-Root)
- 레벨 순회 (BFS)
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}
public static void preorderTraversal(BSTNode current) {
if (current == null)
return;
System.out.print(current.value + " ");
preorderTraversal(current.leftChild);
preorderTraversal(current.rightChild);
}
public static void postorderTraversal(BSTNode current) {
if (current == null)
return;
postorderTraversal(current.leftChild);
postorderTraversal(current.rightChild);
System.out.print(current.value + " ");
}
public static void levelOrderTraversal(BSTNode root) {
Queue<BSTNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
BSTNode temp = queue.poll();
System.out.print(temp.value + " ");
if (temp.leftChild != null)
queue.add(temp.leftChild);
if (temp.rightChild != null)
queue.add(temp.rightChild);
}
}이러한 메서드를 테스트하려면 각 순회 기법을 사용하여 트리를 출력합니다.
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
System.out.print("Inorder Traversal: ");
inorderTraversal(root);
System.out.print("\nPreorder Traversal: ");
preorderTraversal(root);
System.out.print("\nPostorder Traversal: ");
postorderTraversal(root);
System.out.print("\nLevel-order Traversal: ");
levelOrderTraversal(root);
}출력:
Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21요약
이 랩에서는 Java 에서 이진 탐색 트리를 생성하고, 요소를 삽입하고, 요소를 검색하고, 요소를 삭제하고, 순회하는 방법을 배웠습니다.
먼저 이진 탐색 트리의 노드를 나타내는 BSTNode 클래스를 만들었습니다. 그런 다음 이진 탐색 트리에 특정한 알고리즘을 사용하여 삽입, 검색 및 삭제 기능을 구현했습니다. 마지막으로, 중위 순회, 전위 순회, 후위 순회 및 레벨 순회와 같은 다양한 순회 기법을 사용하여 이진 탐색 트리를 순회하는 방법을 배웠습니다.
이러한 개념을 통해 자신만의 Java 프로그램에서 이진 탐색 트리를 구현할 수 있습니다.
