이진 트리, 이진 탐색 트리의 개념

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리로, 노드가 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 구성됩니다. 이진 트리는 크게 포화 이진 트리, 완전 이진 트리, 균형 이진 트리 등으로 나눌 수 있습니다.

• 포화 이진 트리: 모든 레벨에서 노드가 꽉 채워져 있는 트리로, 높이가 h일 때 총 2^(h+1) - 1개의 노드를 가집니다.
• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있으며, 마지막 레벨의 노드는 왼쪽에서 오른쪽으로 채워진 트리입니다.
• 균형 이진 트리: 트리의 모든 리프 노드가 일정한 높이를 가지도록 유지된 트리로, 높이 균형을 통해 검색 효율성을 높입니다.

이진 트리는 이러한 다양한 형태로 구성되어 있으며, 트리의 형태에 따라 탐색, 삽입, 삭제 등의 성능이 달라질 수 있습니다.

이진 탐색 트리(BST)는 이진 트리의 일종으로, 각 노드의 왼쪽 서브트리는 노드보다 작은 값을, 오른쪽 서브트리는 노드보다 큰 값을 가지는 특징이 있습니다. BST는 정렬된 데이터를 효율적으로 검색할 수 있어 데이터 탐색에 유리합니다.

• 탐색(Search): 루트에서 시작하여 찾는 값이 작으면 왼쪽, 크면 오른쪽 서브트리로 이동하며 탐색을 진행합니다.
• 삽입(Insertion): 새로운 값을 가진 노드를 추가할 때, 값의 크기에 따라 왼쪽 또는 오른쪽 자식으로 추가됩니다.
• 삭제(Deletion): 노드를 삭제할 때, 리프 노드인지, 자식이 하나인지, 자식이 둘인지에 따라 다른 방법으로 삭제합니다.

BST의 시간 복잡도는 트리의 균형 여부에 따라 달라집니다. 균형 트리라면 평균 O(log n)이지만, 트리가 한쪽으로 치우친 경우 최악의 경우 O(n)이 될 수 있습니다.

다음은 BST의 기본 연산인 탐색, 삽입, 삭제의 Python 코드 예제입니다.

Python 코드 예제:
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)
        else:
            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 is not None
        if key < node.value:
            return self._search_recursive(node.left, key)
        return self._search_recursive(node.right, key)

    # 삭제 연산
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return node
        if key < node.value:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.value:
            node.right = self._delete_recursive(node.right, key)
        else:
            # 노드가 리프 노드일 경우
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            # 자식이 둘인 경우
            min_larger_node = self._get_min(node.right)
            node.value = min_larger_node.value
            node.right = self._delete_recursive(node.right, min_larger_node.value)
        return node

    def _get_min(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

# 예제 사용
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)
print(bst.search(7))  # 출력: True
bst.delete(7)
print(bst.search(7))  # 출력: False
                

설명: BinarySearchTree 클래스는 BST의 기본 연산을 구현합니다. 삽입 연산은 새로운 노드를 트리에 추가하고, 탐색 연산은 주어진 값이 존재하는지 확인하며, 삭제 연산은 해당 노드를 제거합니다.