이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 한 종류로, 각 노드가 다음과 같은 속성을 만족한다:

1. 왼쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 작다.
2. 오른쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 크다.
3. 각 서브트리도 이진 탐색 트리이다.

이러한 속성 덕분에 이진 탐색 트리는 효율적인 탐색, 삽입, 삭제 연산을 지원한다.

주요 연산

1. 탐색 (Search):
   • 이진 탐색 트리에서 특정 값을 탐색하는 연산이다.
   • 현재 노드와 비교하여 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동한다.
   • 평균 시간 복잡도는 O(log n)이다.
2. 삽입 (Insert):
   • 새로운 값을 트리에 삽입하는 연산이다.
   • 탐색 연산과 유사하게, 삽입할 위치를 찾아 해당 위치에 노드를 추가한다.
   • 평균 시간 복잡도는 O(log n)이다.
3. 삭제 (Delete):
   • 특정 값을 트리에서 삭제하는 연산이다.
   • 세 가지 경우로 나뉜다:
     1. 삭제할 노드가 리프 노드인 경우: 단순히 노드를 제거한다.
     2. 삭제할 노드가 하나의 자식 노드를 가진 경우: 자식 노드를 부모 노드와 연결한다.
     3. 삭제할 노드가 두 개의 자식 노드를 가진 경우: 오른쪽 서브트리에서 가장 작은 값을 가진 노드(또는 왼쪽 서브트리에서 가장 큰 값을 가진 노드)로 대체한 후, 해당 노드를 삭제한다.
   • 평균 시간 복잡도는 O(log n)이다.

이진 탐색 트리의 장점

1. 효율적인 탐색: 이진 탐색 트리의 평균 탐색 시간은 O(log n)으로 매우 효율적이다.
2. 정렬된 데이터: 중위 순회(Inorder Traversal)를 통해 이진 탐색 트리의 모든 노드를 오름차순으로 방문할 수 있다.
3. 동적 데이터 관리: 이진 탐색 트리는 동적으로 데이터를 삽입, 삭제할 수 있어 데이터의 동적 변화에 대응할 수 있다.

이진 탐색 트리의 단점

1. 불균형 트리: 삽입 순서에 따라 트리가 한쪽으로 치우쳐 불균형해질 수 있다. 이 경우 시간 복잡도는 최악의 경우 O(n)이 될 수 있다.
2. 균형 유지 필요: AVL 트리, 레드-블랙 트리와 같은 균형 이진 탐색 트리를 사용하여 트리의 균형을 유지해야 한다.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, root, key):
        if root is None:
            return Node(key)
        if key < root.val:
            root.left = self._insert(root.left, key)
        else:
            root.right = self._insert(root.right, key)
        return root

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, root, key):
        if root is None or root.val == key:
            return root
        if key < root.val:
            return self._search(root.left, key)
        else:
            return self._search(root.right, key)

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, root, key):
        if root is None:
            return root

        if key < root.val:
            root.left = self._delete(root.left, key)
        elif key > root.val:
            root.right = self._delete(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left

            temp = self._min_value_node(root.right)
            root.val = temp.val
            root.right = self._delete(root.right, temp.val)

        return root

    def _min_value_node(self, node):
        if node.left is None:
            return node
        else:
            return self._min_value_node(node.left)

    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print(node.val, end=" ")
            self.inorder(node.right)

bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(2)
bst.insert(7)
bst.insert(12)
bst.insert(18)

print("Inorder traversal:")
bst.inorder(bst.root)  # Output: 2 5 7 10 12 15 18

print("\\nSearch for 7:", bst.search(7))  # Output: <__main__.Node object at ...>
print("Search for 20:", bst.search(20))  # Output: None

bst.delete(10)
print("Inorder traversal after deleting 10:")
bst.inorder(bst.root)  # Output: 2 5 7 12 15 18

주요 메서드 설명

1. insert:
   • 새로운 노드를 삽입한다.
   • 루트가 없으면 루트로 설정하고, 그렇지 않으면 _insert 메서드를 호출하여 올바른 위치에 삽입한다.
2. _insert:
   • 재귀적으로 노드를 삽입할 위치를 찾아 삽입한다.
3. search:
   • 특정 값을 탐색한다.
   • _search 메서드를 호출하여 재귀적으로 탐색한다.
4. _search:
   • 현재 노드가 찾고자 하는 값인지 확인하고, 그렇지 않으면 왼쪽 또는 오른쪽 서브트리로 이동하여 탐색한다.
5. delete:
   • 특정 값을 삭제한다.
   • _delete 메서드를 호출하여 재귀적으로 삭제한다.
6. _delete:
   • 삭제할 노드를 찾고, 노드가 두 자식을 가지면 오른쪽 서브트리에서 최소 값을 찾아 현재 노드를 대체한다.
   • 자식이 하나 또는 없는 경우, 해당 자식을 부모 노드와 연결한다.
7. _min_value_node:
   • 특정 서브트리에서 최소 값을 가진 노드를 찾는다.
8. inorder:
   • 중위 순회(Inorder Traversal)를 수행하여 노드 값을 오름차순으로 출력한다.

이진 탐색 트리는 효율적인 탐색, 삽입, 삭제 연산을 지원하는 강력한 자료 구조이다. 그러나 최악의 경우 O(n)의 시간 복잡도를 가지므로, 균형을 유지하는 AVL 트리나 레드-블랙 트리와 같은 균형 이진 탐색 트리를 사용하는 것이 좋다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms