11월 자료구조 - 이진 탐색 트리 (Binary Search Tree, BST)

 

 

1. 자료구조 주제

이진 탐색 트리 (Binary Search Tree, BST)

 

2. 고른 자료구조의 정의

이진 탐색 트리(BST)는 트리 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다. 이진 탐색 트리는 왼쪽 자식 노드의 값이 부모 노드보다 작고, 오른쪽 자식 노드의 값이 부모 노드보다 크다는 특성을 가집니다. 이 특성 덕분에 이진 탐색 트리는 효율적인 검색, 삽입, 삭제 연산을 수행할 수 있습니다.

BST의 주요 특징은 다음과 같습니다:

• 검색: 루트에서부터 왼쪽 혹은 오른쪽 자식 노드를 따라가며 검색이 이루어집니다.
• 삽입: 적절한 위치를 찾아 값을 삽입합니다.
• 삭제: 삭제할 노드의 자식 노드 수에 따라 다른 방법으로 삭제합니다.

BST의 시간 복잡도는 평균적으로 O(log n)이지만, 트리가 편향되어 있으면 최악의 경우 O(n)이 될 수 있습니다.

 

3. 고른 자료구조를 구현한 파이썬 코드 전문

이진 탐색 트리를 구현한 파이썬 코드는 아래와 같습니다. 이 코드에서는 노드를 삽입하고 검색하는 기능을 포함합니다.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = 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_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        # 값이 작으면 왼쪽 자식에 삽입
        if key < node.value:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert_recursive(node.left, key)
        # 값이 크면 오른쪽 자식에 삽입
        elif key > node.value:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert_recursive(node.right, key)

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

    def _search_recursive(self, node, key):
        if node is None or node.value == key:
            return node
        if key < node.value:
            return self._search_recursive(node.left, key)
        return self._search_recursive(node.right, key)

    def inorder_traversal(self):
        return self._inorder_recursive(self.root)

    def _inorder_recursive(self, node):
        if node is None:
            return []
        return self._inorder_recursive(node.left) + [node.value] + self._inorder_recursive(node.right)

# 예시 사용
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("Inorder traversal:", bst.inorder_traversal())  # 중위 순회 출력
print("Search for 40:", bst.search(40))  # 40을 찾기
print("Search for 100:", bst.search(100))  # 100을 찾기

 

4. 고른 자료구조의 원리를 어떻게 파이썬으로 구현했는지

위 코드는 이진 탐색 트리(BST)를 파이썬으로 구현한 예시입니다. 코드 해설을 해보겠습니다.

• Node 클래스: Node 클래스는 이진 탐색 트리의 각 노드를 나타냅니다. 각 노드는 left, right 자식 노드를 가지며, value는 노드의 값을 저장합니다.
• BinarySearchTree 클래스: BinarySearchTree 클래스는 이진 탐색 트리를 나타내며, 트리의 삽입, 검색, 중위 순회를 위한 메서드를 가지고 있습니다.
• insert 메서드: 이 메서드는 트리에 값을 삽입하는 기능을 합니다. 트리가 비어있으면 루트 노드로 삽입하고, 그렇지 않으면 _insert_recursive를 호출하여 재귀적으로 적절한 위치에 값을 삽입합니다.
• _insert_recursive 메서드: 삽입을 위한 재귀 함수로, 현재 노드의 값과 비교하여 왼쪽 혹은 오른쪽 자식에 값을 삽입합니다. 왼쪽 자식은 현재 노드보다 작은 값을, 오른쪽 자식은 더 큰 값을 가집니다.
• search 메서드: 주어진 키를 트리에서 검색하는 메서드입니다. _search_recursive 메서드를 사용하여 재귀적으로 트리를 탐색합니다.
• _search_recursive 메서드: 검색을 위한 재귀 함수로, 현재 노드가 None일 때까지 탐색을 반복합니다. 찾는 값이 현재 노드의 값과 일치하면 그 노드를 반환합니다.
• inorder_traversal 메서드: 트리의 중위 순회를 반환하는 메서드입니다. _inorder_recursive 메서드를 사용하여 왼쪽 자식, 현재 노드, 오른쪽 자식을 차례대로 방문합니다.

 

5. 느낀점

이진 탐색 트리는 매우 효율적인 자료구조로, 특히 대규모 데이터에서 빠른 검색과 삽입을 가능하게 해줍니다. 재귀적으로 구현된 삽입과 검색 메서드는 이해하기 쉽고 직관적입니다. 하지만 트리가 편향될 경우 성능이 저하될 수 있기 때문에, 균형잡힌 이진 탐색 트리(예: AVL 트리, 레드-블랙 트리)를 고려해야 할 필요성이 있습니다. 이진 탐색 트리를 구현하면서 재귀와 트리 구조에 대해 더 깊이 이해할 수 있었고, 이를 통해 다른 트리 기반 자료구조나 알고리즘을 배울 때 큰 도움이 될 것입니다.