이진 검색 트리 (Binary Search Tree)

이진 검색 트리(Binary Search Tree, BST)는 컴퓨터 과학에서 가장 중요한 자료구조 중 하나로, 효율적인 검색, 삽입, 삭제 연산을 제공하는 이진 트리 형태의 자료구조이다.

이진 검색 트리는 컴퓨터 과학과 소프트웨어 개발에서 중요한 위치를 차지하는 자료구조이다.
그 구조적 단순함과 직관적인 연산에도 불구하고, 효율적인 검색, 삽입, 삭제 및 정렬된 접근을 제공하여 다양한 응용 분야에서 활용되고 있다.

이진 검색 트리의 주요 장점은 다음과 같다:

효율적인 검색 연산: 균형 잡힌 트리에서는 O(log n)의 시간 복잡도로 요소를 검색할 수 있다.
동적인 크기 조정: 삽입과 삭제가 용이하므로 동적으로 변화하는 데이터셋에 적합하다.
정렬된 데이터 접근: 중위 순회를 통해 정렬된 순서로 모든 요소에 접근할 수 있다.
범위 쿼리 효율성: 특정 범위 내의 모든 요소를 효율적으로 찾을 수 있다.
확장성: 자가 균형 트리, 멀티셋 등 다양한 확장과 변형이 가능하다.

그러나 이진 검색 트리에는 몇 가지 단점도 있다:

불균형 가능성: 균형이 무너지면 O(n)의 최악 시간 복잡도를 가질 수 있다.
해시 테이블보다 느린 검색: 해시 테이블은 평균적으로 O(1)의 검색 시간을 제공한다.
추가 메모리 필요: 각 노드는 포인터를 저장하기 위한 추가 메모리가 필요하다.
최적화의 어려움: 최적의 성능을 위해서는 균형 유지 전략이 필요하다.

이러한 장단점을 고려할 때, 이진 검색 트리는 다음과 같은 상황에서 특히 유용하다:

정렬된 데이터 집합을 유지해야 하는 경우
데이터에 대한 범위 쿼리가 자주 필요한 경우
삽입, 삭제, 검색이 모두 빈번하게 발생하는 경우
최악의 경우 성능이 보장되어야 하는 경우(AVL 트리나 레드-블랙 트리 사용 시)

이진 검색 트리의 기본 개념

이진 검색 트리의 정의

이진 검색 트리는 다음과 같은 속성을 만족하는 이진 트리이다:

각 노드는 키(key)를 갖고, 이 키는 해당 노드를 식별하는 고유한 값이다.
모든 노드에 대해, 그 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 해당 노드의 키보다 작다.
모든 노드에 대해, 그 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 해당 노드의 키보다 크다.
왼쪽과 오른쪽 서브트리도 각각 이진 검색 트리이다.

이러한 속성을 통해 이진 검색 트리는 정렬된 데이터를 효율적으로 저장하고 검색할 수 있다.

이진 검색 트리의 구조

이진 검색 트리의 구조는 다음과 같다:

1
2
3
4
5
6
7
        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

이 트리는 이진 검색 트리의 속성을 만족한다:

노드 8의 왼쪽 서브트리(3, 1, 6, 4, 7)의 모든 값은 8보다 작다.
노드 8의 오른쪽 서브트리(10, 14, 13)의 모든 값은 8보다 크다.
각 서브트리도 이진 검색 트리이다.

이진 검색 트리의 기본 구현(Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TreeNode:
    def __init__(self, key):
        self.key = key          # 노드의 키 값
        self.left = None        # 왼쪽 자식 노드
        self.right = None       # 오른쪽 자식 노드
        
    def __str__(self):
        return str(self.key)

class BinarySearchTree:
    def __init__(self):
        self.root = None        # 트리의 루트 노드
    
    # 기본 연산들은 다음 섹션에서 구현할 예정입니다.

Binary Search Tree — https://www.geeksforgeeks.org/introduction-to-binary-search-tree/?ref=lbp

이진 검색 트리의 기본 연산

검색(Search)

이진 검색 트리에서 특정 키를 가진 노드를 검색하는 연산이다.
트리의 특성을 활용하여 효율적인 검색이 가능하다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def search(self, key):
    """이진 검색 트리에서 키 값을 검색"""
    return self._search_recursive(self.root, key)

def _search_recursive(self, node, key):
    # 기본 경우: 노드가 없거나 찾는 키와 일치하는 경우
    if node is None or node.key == key:
        return node
    
    # 키가 현재 노드보다 작으면 왼쪽 서브트리에서 검색
    if key < node.key:
        return self._search_recursive(node.left, key)
    # 키가 현재 노드보다 크면 오른쪽 서브트리에서 검색
    else:
        return self._search_recursive(node.right, key)

비재귀적 검색 방법:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def search_iterative(self, key):
    """이진 검색 트리에서 키 값을 반복적으로 검색"""
    current = self.root
    
    while current is not None:
        if current.key == key:
            return current
        elif key < current.key:
            current = current.left
        else:
            current = current.right
    
    return None  # 키를 찾지 못한 경우

삽입(Insertion)

이진 검색 트리에 새로운 노드를 삽입하는 연산이다.
트리의 특성을 유지하면서 적절한 위치에 노드를 삽입한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def insert(self, key):
    """이진 검색 트리에 키 삽입"""
    self.root = self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
    # 삽입 위치에 도달한 경우 새 노드 생성
    if node is None:
        return TreeNode(key)
    
    # 키가 현재 노드보다 작으면 왼쪽 서브트리에 삽입
    if key < node.key:
        node.left = self._insert_recursive(node.left, key)
    # 키가 현재 노드보다 크면 오른쪽 서브트리에 삽입
    elif key > node.key:
        node.right = self._insert_recursive(node.right, key)
    # 키가 이미 존재하는 경우 (중복 처리 방식에 따라 다름)
    else:
        return node  # 중복 무시 (또는 다른 처리)
    
    return node

비재귀적 삽입 방법:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def insert_iterative(self, key):
    """이진 검색 트리에 키를 반복적으로 삽입"""
    new_node = TreeNode(key)
    
    # 트리가 비어있는 경우
    if self.root is None:
        self.root = new_node
        return
    
    current = self.root
    parent = None
    
    while current is not None:
        parent = current
        
        if key < current.key:
            current = current.left
        elif key > current.key:
            current = current.right
        else:
            return  # 중복 키는 무시 (또는 다른 처리)
    
    # 새 노드를 부모 노드에 연결
    if key < parent.key:
        parent.left = new_node
    else:
        parent.right = new_node

삭제(Deletion)

이진 검색 트리에서 노드를 삭제하는 연산은 세 가지 경우로 나눌 수 있다:

삭제할 노드가 리프 노드인 경우
삭제할 노드가 하나의 자식을 가진 경우
삭제할 노드가 두 개의 자식을 가진 경우

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def delete(self, key):
    """이진 검색 트리에서 키 삭제"""
    self.root = self._delete_recursive(self.root, key)

def _delete_recursive(self, node, key):
    # 기본 경우: 키를 찾지 못한 경우
    if node is None:
        return None
    
    # 삭제할 키 찾기
    if key < node.key:
        node.left = self._delete_recursive(node.left, key)
    elif key > node.key:
        node.right = self._delete_recursive(node.right, key)
    else:
        # 삭제할 노드를 찾은 경우
        
        # 경우 1 & 2: 자식이 없거나 하나인 경우
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        
        # 경우 3: 두 자식이 있는 경우
        # 중위 후속자(오른쪽 서브트리에서 가장 작은 노드)를 찾음
        successor = self._find_min(node.right)
        node.key = successor.key  # 후속자의 키를 현재 노드로 복사
        
        # 중위 후속자 삭제
        node.right = self._delete_recursive(node.right, successor.key)
    
    return node

def _find_min(self, node):
    """트리의 최소값(가장 왼쪽) 노드 찾기"""
    current = node
    while current.left is not None:
        current = current.left
    return current

순회(Traversal)

이진 검색 트리의 모든 노드를 방문하는 방법은 다음과 같다:

중위 순회(Inorder Traversal)

왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순으로 방문한다.
이진 검색 트리에서 중위 순회를 하면 정렬된 순서로 키를 얻을 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def inorder_traversal(self):
    """중위 순회로 노드 방문 (정렬된 순서)"""
    result = []
    self._inorder_recursive(self.root, result)
    return result

def _inorder_recursive(self, node, result):
    if node is not None:
        self._inorder_recursive(node.left, result)  # 왼쪽 서브트리 방문
        result.append(node.key)                    # 현재 노드 방문
        self._inorder_recursive(node.right, result) # 오른쪽 서브트리 방문

전위 순회(Preorder Traversal)

현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 방문한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def preorder_traversal(self):
    """전위 순회로 노드 방문"""
    result = []
    self._preorder_recursive(self.root, result)
    return result

def _preorder_recursive(self, node, result):
    if node is not None:
        result.append(node.key)                     # 현재 노드 방문
        self._preorder_recursive(node.left, result)  # 왼쪽 서브트리 방문
        self._preorder_recursive(node.right, result) # 오른쪽 서브트리 방문

후위 순회(Postorder Traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드 순으로 방문한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def postorder_traversal(self):
    """후위 순회로 노드 방문"""
    result = []
    self._postorder_recursive(self.root, result)
    return result

def _postorder_recursive(self, node, result):
    if node is not None:
        self._postorder_recursive(node.left, result)  # 왼쪽 서브트리 방문
        self._postorder_recursive(node.right, result) # 오른쪽 서브트리 방문
        result.append(node.key)                     # 현재 노드 방문

최솟값과 최댓값 찾기

이진 검색 트리에서 최솟값은 가장 왼쪽 노드, 최댓값은 가장 오른쪽 노드에 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def find_min(self):
    """트리의 최소 키 값 찾기"""
    if self.root is None:
        return None
    
    current = self.root
    while current.left is not None:
        current = current.left
    
    return current.key

def find_max(self):
    """트리의 최대 키 값 찾기"""
    if self.root is None:
        return None
    
    current = self.root
    while current.right is not None:
        current = current.right
    
    return current.key

이진 검색 트리의 시간 복잡도

이진 검색 트리의 성능은 트리의 형태(균형 정도)에 크게 의존한다.

평균 시간 복잡도

트리가 어느 정도 균형을 유지하는 경우:

검색: O(log n)
삽입: O(log n)
삭제: O(log n)
순회: O(n)

이는 각 연산에서 트리의 높이에 비례하는 노드만 방문하기 때문이다.

3.2 최악 시간 복잡도

트리가 한쪽으로 치우친 경우(skewed tree):

검색: O(n)
삽입: O(n)
삭제: O(n)
순회: O(n)

예를 들어, 정렬된 데이터를 순서대로 삽입하면 다음과 같은 편향된 트리가 생성된다.

이런 경우 트리는 사실상 연결 리스트처럼 동작하며, 연산 효율성이 크게 저하된다.

이진 검색 트리의 균형 개념

균형과 불균형

이진 검색 트리의 효율성은 그 균형 상태에 크게 의존한다:

균형 트리: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 일정 범위 내에 있는 트리
불균형(편향) 트리: 한쪽으로 치우쳐진 트리로, 연결 리스트와 유사한 성능을 보임

균형 요소(Balance Factor)

노드의 균형 요소는 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이로 정의된다:

`1`	`균형 요소(BF) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이`

완전히 균형 잡힌 트리에서는 모든 노드의 균형 요소가 -1, 0, 또는 1이다다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def get_height(self, node):
    """노드의 높이 계산"""
    if node is None:
        return -1
    return max(self.get_height(node.left), self.get_height(node.right)) + 1

def get_balance_factor(self, node):
    """노드의 균형 요소 계산"""
    if node is None:
        return 0
    return self.get_height(node.left) - self.get_height(node.right)

자가 균형 이진 검색 트리(Self-Balancing BST)

이진 검색 트리의 불균형 문제를 해결하기 위해 자가 균형 이진 검색 트리가 개발되었다.
이들은 삽입과 삭제 연산 중에 자동으로 트리의 균형을 유지한다.

AVL 트리

AVL 트리는 모든 노드의 균형 요소가 -1, 0, 1 중 하나인 이진 검색 트리이다.
균형이 깨질 경우 회전 연산을 통해 균형을 회복한다.

회전 연산에는 네 가지 유형이 있다:

좌회전(Left Rotation)
우회전(Right Rotation)
좌-우회전(Left-Right Rotation)
우-좌회전(Right-Left Rotation)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class AVLNode(TreeNode):
    def __init__(self, key):
        super().__init__(key)
        self.height = 0  # 노드의 높이

class AVLTree(BinarySearchTree):
    def __init__(self):
        super().__init__()
    
    def _get_height(self, node):
        if node is None:
            return -1
        return node.height
    
    def _update_height(self, node):
        if node is not None:
            node.height = max(self._get_height(node.left), self._get_height(node.right)) + 1
    
    def _get_balance(self, node):
        if node is None:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)
    
    def _left_rotate(self, x):
        y = x.right
        T2 = y.left
        
        # 회전 수행
        y.left = x
        x.right = T2
        
        # 높이 업데이트
        self._update_height(x)
        self._update_height(y)
        
        return y  # 새 루트 반환
    
    def _right_rotate(self, y):
        x = y.left
        T2 = x.right
        
        # 회전 수행
        x.right = y
        y.left = T2
        
        # 높이 업데이트
        self._update_height(y)
        self._update_height(x)
        
        return x  # 새 루트 반환
    
    def insert(self, key):
        """AVL 트리에 키 삽입"""
        self.root = self._insert_recursive(self.root, key)
    
    def _insert_recursive(self, node, key):
        # 일반 BST 삽입
        if node is None:
            return AVLNode(key)
        
        if key < node.key:
            node.left = self._insert_recursive(node.left, key)
        elif key > node.key:
            node.right = self._insert_recursive(node.right, key)
        else:
            return node  # 중복 키는 무시
        
        # 노드 높이 업데이트
        self._update_height(node)
        
        # 균형 요소 확인
        balance = self._get_balance(node)
        
        # 균형이 깨진 경우 회전으로 복구
        
        # 좌-좌 케이스
        if balance > 1 and key < node.left.key:
            return self._right_rotate(node)
        
        # 우-우 케이스
        if balance < -1 and key > node.right.key:
            return self._left_rotate(node)
        
        # 좌-우 케이스
        if balance > 1 and key > node.left.key:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)
        
        # 우-좌 케이스
        if balance < -1 and key < node.right.key:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)
        
        return node

레드-블랙 트리(Red-Black Tree)

레드-블랙 트리는 각 노드에 추가적인 색상 속성(빨간색 또는 검은색)을 부여하여 균형을 유지하는 이진 검색 트리이다.

다음과 같은 속성을 만족한다:

모든 노드는 빨간색 또는 검은색.
루트 노드는 검은색.
모든 리프 노드(NIL)는 검은색.
빨간색 노드의 자식은 모두 검은색(빨간색 노드가 연속으로 나타나지 않음).
임의의 노드에서 그 노드의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 검은색 노드가 있다.

레드-블랙 트리의 삽입과 삭제 연산은 색상 변경과 회전을 통해 위의 속성을 유지한다.

B-트리와 B+트리

B-트리와 B+트리는 이진 검색 트리의 개념을 확장한 다중 분기 검색 트리로, 주로 디스크 기반 저장 시스템(데이터베이스, 파일 시스템)에서 사용된다.

이진 검색 트리의 응용

우선순위 큐(Priority Queue)
이진 검색 트리를 사용하여 우선순위 큐를 구현할 수 있다.
각 요소의 우선순위는 키 값으로 표현된다.
심볼 테이블(Symbol Table)
컴파일러는 변수, 함수 등의 식별자 정보를 저장하기 위해 심볼 테이블을 사용하며, 이는 종종 이진 검색 트리로 구현된다.
데이터베이스 인덱싱
많은 데이터베이스 시스템은 B-트리나 B+트리(이진 검색 트리의 변형)를 사용하여 인덱스를 구현한다.

맵과 셋(Map and Set)
많은 프로그래밍 언어의 표준 라이브러리에서 맵(map)과 셋(set) 자료구조는 이진 검색 트리나 그 변형으로 구현된다.

1
2
3
4
5
6
# Python의 collections 모듈에 있는 OrderedDict는 내부적으로 이진 검색 트리와 
# 유사한 자료구조를 사용합니다(실제로는 해시 테이블과 연결 리스트의 조합이지만 개념적으로 유사)
from collections import OrderedDict

# Java의 TreeMap과 TreeSet은 레드-블랙 트리로 구현됩니다
# C++의 std::map과 std::set도 균형 이진 검색 트리(주로 레드-블랙 트리)로 구현됩니다

이진 검색 트리의 구현 예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
    def _preorder_recursive(self, node, result):
        if node is not None:
            result.append(node.key)                     # 현재 노드 방문
            self._preorder_recursive(node.left, result)  # 왼쪽 서브트리 방문
            self._preorder_recursive(node.right, result) # 오른쪽 서브트리 방문
    
    def postorder_traversal(self):
        """후위 순회로 노드 방문"""
        result = []
        self._postorder_recursive(self.root, result)
        return result
    
    def _postorder_recursive(self, node, result):
        if node is not None:
            self._postorder_recursive(node.left, result)  # 왼쪽 서브트리 방문
            self._postorder_recursive(node.right, result) # 오른쪽 서브트리 방문
            result.append(node.key)                     # 현재 노드 방문
    
    def get_height(self):
        """트리의 높이 계산"""
        return self._height_recursive(self.root)
    
    def _height_recursive(self, node):
        if node is None:
            return -1
        
        left_height = self._height_recursive(node.left)
        right_height = self._height_recursive(node.right)
        
        return max(left_height, right_height) + 1
    
    def is_bst(self):
        """이진 검색 트리 속성을 만족하는지 확인"""
        return self._is_bst_recursive(self.root, float('-inf'), float('inf'))
    
    def _is_bst_recursive(self, node, min_val, max_val):
        # 빈 트리는 BST 속성을 만족
        if node is None:
            return True
        
        # 현재 노드가 범위를 벗어나면 BST가 아님
        if node.key <= min_val or node.key >= max_val:
            return False
        
        # 왼쪽과 오른쪽 서브트리가 BST인지 재귀적으로 확인
        return (self._is_bst_recursive(node.left, min_val, node.key) and
                self._is_bst_recursive(node.right, node.key, max_val))

이진 검색 트리의 고급 연산

이진 검색 트리에서 수행할 수 있는 몇 가지 고급 연산.

범위 쿼리(Range Query)
주어진 범위 내의 모든 키를 찾는 연산.
`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def range_query(self, low, high):
    """low와 high 사이의 모든 키 값 반환"""
    result = []
    self._range_query_recursive(self.root, low, high, result)
    return result

def _range_query_recursive(self, node, low, high, result):
    if node is None:
        return

    # 현재 노드가 범위 내에 있는지 확인
    if low <= node.key <= high:
        # 중위 순회와 유사한 방식으로 진행
        self._range_query_recursive(node.left, low, high, result)  # 왼쪽 서브트리 탐색
        result.append(node.key)                                  # 현재 노드 추가
        self._range_query_recursive(node.right, low, high, result)  # 오른쪽 서브트리 탐색

    # 현재 노드가 범위보다 크면 왼쪽 서브트리만 탐색
    elif node.key > high:
        self._range_query_recursive(node.left, low, high, result)

    # 현재 노드가 범위보다 작으면 오른쪽 서브트리만 탐색
    elif node.key < low:
        self._range_query_recursive(node.right, low, high, result)

순위 쿼리(Rank Query)
주어진 키보다 작은 키의 개수를 찾는 연산.
이를 구현하려면 각 노드가 자신의 왼쪽 서브트리에 있는 노드의 수를 추적해야 한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class RankTreeNode(TreeNode):
    def __init__(self, key):
        super().__init__(key)
        self.left_size = 0  # 왼쪽 서브트리의 노드 수

class RankBST(BinarySearchTree):
    def __init__(self):
        super().__init__()

    def insert(self, key):
        """순위 정보를 유지하며 키 삽입"""
        self.root = self._insert_with_rank(self.root, key)

    def _insert_with_rank(self, node, key):
        if node is None:
            return RankTreeNode(key)

        if key < node.key:
            node.left = self._insert_with_rank(node.left, key)
            node.left_size += 1  # 왼쪽 서브트리에 노드 추가
        elif key > node.key:
            node.right = self._insert_with_rank(node.right, key)

        return node

    def rank(self, key):
        """주어진 키보다 작은 키의 개수"""
        return self._rank_recursive(self.root, key)

    def _rank_recursive(self, node, key):
        if node is None:
            return 0

        if key < node.key:
            return self._rank_recursive(node.left, key)
        elif key > node.key:
            # 현재 노드와 왼쪽 서브트리의 크기 + 오른쪽 서브트리의 순위
            return node.left_size + 1 + self._rank_recursive(node.right, key)
        else:  # key == node.key
            return node.left_size

근사 검색(Nearest Neighbor Search)
주어진 키에 가장 가까운 키를 찾는 연산.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def find_nearest(self, key):
    """주어진 키에 가장 가까운 키 찾기"""
    if self.root is None:
        return None

    nearest = self.root.key
    min_diff = abs(key - nearest)

    current = self.root
    while current is not None:
        # 현재 노드와 키 사이의 차이 계산
        current_diff = abs(key - current.key)

        # 더 가까운 노드를 찾으면 업데이트
        if current_diff < min_diff:
            nearest = current.key
            min_diff = current_diff

        # 키가 같으면 정확한 일치를 찾은 것이므로 종료
        if current.key == key:
            return key

        # 트리를 순회
        if key < current.key:
            current = current.left
        else:
            current = current.right

    return nearest

이진 검색 트리를 사용한 동적 집합 연산
이진 검색 트리는 집합이나 맵 자료구조를 구현하는 데 사용될 수 있으며, 다음과 같은 동적 집합 연산을 지원한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def union(self, other_bst):
    """두 BST의 합집합"""
    # 다른 BST의 모든 노드를 현재 BST에 삽입
    elements = other_bst.inorder_traversal()
    for key in elements:
        self.insert(key)

def intersection(self, other_bst):
    """두 BST의 교집합"""
    result = BinarySearchTree()
    elements = self.inorder_traversal()

    # 현재 BST의 요소 중 다른 BST에도 있는 요소만 삽입
    for key in elements:
        if other_bst.search(key):
            result.insert(key)

    return result

def difference(self, other_bst):
    """현재 BST에서 다른 BST의 요소를 제외한 차집합"""
    result = BinarySearchTree()
    elements = self.inorder_traversal()

    # 현재 BST의 요소 중 다른 BST에 없는 요소만 삽입
    for key in elements:
        if not other_bst.search(key):
            result.insert(key)

    return result

이진 검색 트리를 통한 문제 해결

이진 검색 트리를 활용하여 다양한 문제를 해결하는 방법.

이진 검색 트리에서의 두 노드 간 최소 거리
이진 검색 트리에서 두 키 값 사이의 최소 거리를 찾는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def min_distance(self):
    """BST에서 인접한 키 사이의 최소 거리"""
    # 중위 순회로 정렬된 키 목록 얻기
    keys = self.inorder_traversal()

    if len(keys) < 2:
        return float('inf')  # 노드가 부족한 경우

    min_diff = float('inf')
    for i in range(1, len(keys)):
        diff = keys[i] - keys[i-1]
        min_diff = min(min_diff, diff)

    return min_diff

이진 검색 트리의 K번째 작은 요소
이진 검색 트리에서 k번째로 작은 요소를 찾는 문제.

1
2
3
4
5
6
7
8
9
def kth_smallest(self, k):
    """BST에서 k번째로 작은 요소"""
    # 중위 순회로 정렬된 키 목록 얻기
    keys = self.inorder_traversal()

    if 1 <= k <= len(keys):
        return keys[k-1]
    else:
        return None  # k가 범위를 벗어나면 None 반환

노드에 추가 정보를 저장하면 더 효율적으로 구현할 수 있다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def kth_smallest_optimized(self, k):
    """BST에서 k번째로 작은 요소 (최적화 버전)"""
    count = [0]  # 방문한 노드 수 추적
    result = [None]  # 결과 저장용 변수 (배열로 전달하여 변경 가능하게 함)

    def inorder(node):
        if node is None or count[0] >= k:
            return

        inorder(node.left)

        count[0] += 1
        if count[0] == k:
            result[0] = node.key
            return

        inorder(node.right)

    inorder(self.root)
    return result[0]

이진 검색 트리의 두 노드 사이의 최소 공통 조상(LCA)
두 노드의 가장 가까운 공통 조상을 찾는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def lowest_common_ancestor(self, p, q):
    """두 키의 최소 공통 조상 찾기"""
    return self._lca_recursive(self.root, p, q)

def _lca_recursive(self, node, p, q):
    # 기본 경우
    if node is None:
        return None

    # 둘 다 현재 노드보다 작으면 왼쪽 서브트리에서 LCA 찾기
    if p < node.key and q < node.key:
        return self._lca_recursive(node.left, p, q)

    # 둘 다 현재 노드보다 크면 오른쪽 서브트리에서 LCA 찾기
    if p > node.key and q > node.key:
        return self._lca_recursive(node.right, p, q)

    # 현재 노드가 두 키 사이에 있거나 둘 중 하나와 같으면 LCA
    return node.key

이진 검색 트리의 변형과 응용

키-값 저장을 위한 이진 검색 트리

이진 검색 트리를 사용하여 키-값 쌍을 저장하는 맵(Map)을 구현할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MapNode:
    def __init__(self, key, value):
        self.key = key           # 검색에 사용되는 키
        self.value = value       # 키와 연관된 값
        self.left = None
        self.right = None

class TreeMap:
    def __init__(self):
        self.root = None
    
    def put(self, key, value):
        """키-값 쌍 삽입 또는 업데이트"""
        self.root = self._put_recursive(self.root, key, value)
    
    def _put_recursive(self, node, key, value):
        if node is None:
            return MapNode(key, value)
        
        if key < node.key:
            node.left = self._put_recursive(node.left, key, value)
        elif key > node.key:
            node.right = self._put_recursive(node.right, key, value)
        else:
            node.value = value  # 키가 존재하면 값 업데이트
        
        return node
    
    def get(self, key):
        """키에 해당하는 값 검색"""
        node = self._get_recursive(self.root, key)
        return node.value if node else None
    
    def _get_recursive(self, node, key):
        if node is None:
            return None
        
        if key < node.key:
            return self._get_recursive(node.left, key)
        elif key > node.key:
            return self._get_recursive(node.right, key)
        else:
            return node
    
    def delete(self, key):
        """키-값 쌍 삭제"""
        self.root = self._delete_recursive(self.root, key)
    
    def _delete_recursive(self, node, key):
        # 기본 삭제 로직은 일반 BST와 동일
        # …

이진 검색 트리를 사용한 세트(Set) 구현

고유한 키 집합을 저장하기 위한 세트 자료구조를 구현할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TreeSet:
    def __init__(self):
        self.bst = BinarySearchTree()  # 내부적으로 BST 사용
    
    def add(self, key):
        """세트에 키 추가"""
        self.bst.insert(key)
    
    def contains(self, key):
        """세트에 키가 포함되어 있는지 확인"""
        return self.bst.search(key)
    
    def remove(self, key):
        """세트에서 키 제거"""
        self.bst.delete(key)
    
    def size(self):
        """세트에 있는 요소 수"""
        return len(self.bst.inorder_traversal())
    
    def to_list(self):
        """세트의 모든 요소를 정렬된 목록으로 반환"""
        return self.bst.inorder_traversal()

멀티셋(MultiSet) 구현

중복 키를 허용하는 멀티셋을 구현할 수 있다.
각 노드에 키와 해당 키의 빈도수를 저장한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class MultiSetNode:
    def __init__(self, key, count=1):
        self.key = key         # 키 값
        self.count = count     # 키의 빈도수
        self.left = None
        self.right = None

class MultiSet:
    def __init__(self):
        self.root = None
        self.size = 0  # 총 요소 수 (중복 포함)
    
    def add(self, key):
        """멀티셋에 키 추가"""
        result = self._add_recursive(self.root, key)
        self.root = result[0]
        self.size += result[1]  # 크기 증가 여부
    
    def _add_recursive(self, node, key):
        if node is None:
            return (MultiSetNode(key), 1)  # (새 노드, 크기 증가 1)
        
        size_change = 0
        if key < node.key:
            result = self._add_recursive(node.left, key)
            node.left = result[0]
            size_change = result[1]
        elif key > node.key:
            result = self._add_recursive(node.right, key)
            node.right = result[0]
            size_change = result[1]
        else:
            node.count += 1  # 키가 존재하면 카운트 증가
            size_change = 1
        
        return (node, size_change)
    
    def remove(self, key):
        """멀티셋에서 키 하나 제거"""
        if self.root is None:
            return
        
        result = self._remove_recursive(self.root, key)
        self.root = result[0]
        self.size -= result[1]  # 크기 감소 여부
    
    def _remove_recursive(self, node, key):
        if node is None:
            return (None, 0)  # (노드 없음, 크기 변화 없음)
        
        size_change = 0
        if key < node.key:
            result = self._remove_recursive(node.left, key)
            node.left = result[0]
            size_change = result[1]
        elif key > node.key:
            result = self._remove_recursive(node.right, key)
            node.right = result[0]
            size_change = result[1]
        else:
            # 키를 찾은 경우
            if node.count > 1:
                node.count -= 1  # 카운트 감소
                size_change = 1
            else:
                # 노드 삭제 (기본 BST 삭제 로직)
                # …
                size_change = 1
        
        return (node, size_change)
    
    def count(self, key):
        """멀티셋에서 키의 빈도수"""
        node = self._find_node(self.root, key)
        return node.count if node else 0
    
    def _find_node(self, node, key):
        if node is None:
            return None
        
        if key < node.key:
            return self._find_node(node.left, key)
        elif key > node.key:
            return self._find_node(node.right, key)
        else:
            return node

이진 검색 트리의 실제 응용

이진 검색 트리는 다양한 실제 응용 분야에서 사용된다.

데이터베이스 색인(Database Indexing)
관계형 데이터베이스는 B-트리, B+트리와 같은 이진 검색 트리의 변형을 사용하여 레코드를 효율적으로 검색, 삽입, 삭제할 수 있도록 한다.
컴파일러의 심볼 테이블(Symbol Table)
컴파일러는 변수, 함수, 클래스 등의 식별자 정보를 저장하고 빠르게 접근하기 위해 이진 검색 트리 기반의 심볼 테이블을 사용한다.
자동 완성 시스템(Autocomplete System)
검색 엔진이나 텍스트 편집기에서 자동 완성 기능은 트라이(Trie)나 이진 검색 트리를 사용하여 구현된다.
파일 시스템 디렉토리 구조
파일 시스템의 디렉토리 구조는 종종 트리 구조로 표현되며, 파일 검색을 위해 이진 검색 트리 알고리즘이 사용된다.

이진 검색 트리의 성능 최적화

균형 유지 전략
이진 검색 트리의 성능을 최적화하는 가장 중요한 전략은 트리의 균형을 유지하는 것이다.
1. 자가 균형 트리 사용: AVL 트리, 레드-블랙 트리와 같은 자가 균형 이진 검색 트리를 사용한다.
2. 랜덤화된 삽입: 데이터를 삽입하기 전에 무작위로 섞어 균형 잡힌 트리가 생성될 가능성을 높인다.
3. 주기적인 재구성: 불균형이 감지되면 트리를 재구성한다.

노드 캐싱(Node Caching)
자주 접근하는 노드를 캐시하여 검색 성능을 향상시킬 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class CachingBST(BinarySearchTree):
    def __init__(self, cache_size=10):
        super().__init__()
        self.cache = {}  # 키-노드 캐시
        self.cache_size = cache_size
        self.access_count = {}  # 각 키의 접근 횟수

    def search(self, key):
        # 캐시에서 먼저 검색
        if key in self.cache:
            self.access_count[key] += 1
            return True

        # 트리에서 검색
        found = super().search(key)

        # 찾았으면 캐시에 추가
        if found:
            self._add_to_cache(key)

        return found

    def _add_to_cache(self, key):
        # 캐시가 가득 찼으면 가장 적게 접근한 항목 제거
        if len(self.cache) >= self.cache_size:
            min_key = min(self.access_count.items(), key=lambda x: x[1])[0]
            del self.cache[min_key]
            del self.access_count[min_key]

        # 캐시에 노드 추가
        node = self._search_recursive(self.root, key)
        self.cache[key] = node
        self.access_count[key] = 1

병렬 처리(Parallel Processing)
이진 검색 트리의 연산을 병렬화하여 성능을 향상시킬 수 있다.
예를 들어, 큰 데이터셋을 여러 서브트리로 분할하고 각 서브트리를 병렬로 처리할 수 있다.

이진 검색 트리의 미래 발전

이진 검색 트리는 계속해서 발전하고 있으며, 새로운 응용 분야와 최적화 기법이 등장하고 있다.

분산 및 병렬 이진 검색 트리
대규모 분산 시스템에서는 이진 검색 트리를 여러 노드에 분산시켜 병렬로 처리하는 기법이 연구되고 있다. 이는 빅데이터 처리와 클라우드 컴퓨팅에서 중요한 역할을 한다.
지속성 이진 검색 트리(Persistent BST)
지속성(persistence) 이진 검색 트리는 모든 버전의 트리를 유지하면서 효율적인 접근을 제공한다.
이러한 트리는 버전 관리 시스템이나 함수형 프로그래밍에서 유용하다.
양자 검색 트리(Quantum Search Tree)
양자 컴퓨팅의 발전으로 양자 알고리즘을 활용한 이진 검색 트리가 연구되고 있다.
이는 기존 이진 검색 트리보다 더 빠른 검색 및 계산을 제공할 수 있다.