이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리는 항상 정렬된 상태를 유지하는 자료구조이다.
이진 탐색 트리의 정의
- 모든 노드의 키는 중복이 없는 유일한 키를 가진다.
- 왼쪽 서브 트리는 부모 기준 노드보다 작은 값으로 이루어져 있다.
- 오른쪽 서브 트리는 부모 기준 노드보다 큰 값으로 이루어져 있다.
- 왼쪽, 오른쪽 서브 트리 모두 이진 탐색 트리이다.
이진 탐색 트리의 시간 복잡도
BST의 평균 시간 복잡도는 O(log n)이지만, 트리가 균형적이지 않을 경우 최악의 경우(편향 이진 트리)에는 O(n)까지 늘어날 수 있다. 이를 해결하기 위해 균형 이진 탐색 트리(AVL 트리, 레드-블랙 트리 등)와 같은 특별한 형태의 이진 탐색 트리가 개발되었다.
이진 탐색 트리 코드
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
95
96
97
98
99
100
101
102
103
104
105
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
# 전위 순회
def preorder_traversal(self, root):
if root is not None:
print(root.val, end=" ")
self.preorder_traversal(root.left)
self.preorder_traversal(root.right)
# 중위 순회
def inorder_traversal(self, root):
if root is not None:
self.inorder_traversal(root.left)
print(root.val, end=" ")
self.inorder_traversal(root.right)
# 후위 순회
def postorder_traversal(self, root):
if root is not None:
self.postorder_traversal(root.left)
self.postorder_traversal(root.right)
print(root.val, end=" ")
def insert(self, root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = self.insert(root.left, val)
else:
root.right = self.insert(root.right, val)
return root
def insertValue(self, val):
self.root = self.insert(self.root, val)
def search(self, root, val):
if root is None or root.val == val:
return root
if root.val < val:
return self.search(root.right, val)
return self.search(root.left, val)
def searchValue(self, val):
return self.search(self.root, val)
def delete(self, root, val):
if root is None:
return root
if val < root.val:
root.left = self.delete(root.left, val)
elif val > root.val:
root.right = self.delete(root.right, val)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
# 삭제할 노드의 값을 오른쪽 서브트리에서 가장 작은 값으로 대체하고
# 오른쪽 서브트리에서 대체한 값의 노드를 재귀적으로 삭제
root.val = self.minValueNode(root.right).val
root.right = self.delete(root.right, root.val)
return root
def deleteValue(self, val):
self.root = self.delete(self.root, val)
def minValueNode(self, node):
current = node
while current.left is not None:
current = current.left
return current
# example
bst = BST()
values = [5, 3, 8, 1, 4, 7, 9]
for val in values:
bst.insertValue(val)
search_result = bst.searchValue(4)
if search_result:
print("found!")
else:
print("Value 4 not found.")
bst.preorder_traversal(bst.root)
print("\n")
bst.deleteValue(4)
bst.preorder_traversal(bst.root)
insertValue, searchValue, deleteValue들의 함수는 클래스를 사용하는 사용자에게 더 편리하게 하기위하여 만든 함수이다. root노드를 직접 다루지 않고, 값만 전달하면 되기때문에 코드를 좀 더 사용하기 쉽게한다.
이진 탐색 트리 삽입(Insert)
1
2
3
4
5
6
7
8
9
10
def insert(self, root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = self.insert(root.left, val)
else:
root.right = self.insert(root.right, val)
return root
- 루트 노드부터 시작하여 현재 노드와 삽입하려는 데이터를 비교한다.
- 만약 삽이하려는 데이터가 현재 노드의 데이터보다 작으면 왼쪽 서브트리로 이동하고, 크면 오른쪽 서브트리로 이동한다.
- 이동한 서브트리에서 위의 두 단계를 반복한다.
- 비어있는 위치(노드)를 찾았을 때, 그 위치에 데이터를 저장한다.
이진 탐색 트리 탐색(Search)
1
2
3
4
5
6
7
8
def search(self, root, val):
if root is None or root.val == val:
return root
if root.val < val:
return self.search(root.right, val)
return self.search(root.left, val)
- 루트 노드부터 시작하여 현재 노드와 검색하려는 데이터를 비교한다.
- 만약 현재 노드의 데이터가 검색하려는 데이터와 일치하면 검색을 종료한다.
- 현재 노드의 데이터가 검색하려는 데이터보다 작으면, 오른쪽 서브트리로 이동하고, 크면 왼쪽 서브트리로 이동하여 검색을 계속한다.
- 검색을 계속하여 데이터를 찾거나, 해당 노드가 존재하지 않는 경우에는 데이터가 트리에 없음을 나타낸다.
이진 트리 탐색 삭제(Delete)
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 delete(self, root, val):
if root is None:
return root
if val < root.val:
root.left = self.delete(root.left, val)
elif val > root.val:
root.right = self.delete(root.right, val)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
root.val = self.minValueNode(root.right).val
root.right = self.delete(root.right, root.val)
return root
def minValueNode(self, node):
current = node
while current.left is not None:
current = current.left
return current
BST에서 데이터를 삭제하는 연산은 고려해야 할 상황이 있다.
삭제하려는 노드가 단말 노드인 경우(자식이 없는 경우)
그냥 노드를 삭제하면 된다.
삭제하려는 노드가 하나의 자식을 갖는 경우
삭제하려는 노드를 그 자식 노드로 대체한다.
삭제하려는 노드가 두개의 자식을 가지는 경우
삭제하려는 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드(또는 왼쪽 서브트리에서 가장 큰 값을 가진 노드)를 찾아와 삭제하려는 노드의 위치에 대체한다. 이 노드를 찾는 과정은 오른쪽 서브트리에서 가장 왼쪽 노드로 이동하거나, 왼쪽 서브트리에서 가장 오른쪽 노드로 이동하는 방식으로 수행된다.
회고 및 참고
이진 탐색 트리는 개념만 알고, 문제를 풀지는 않아봤는데, 생각보다 잘 풀릴듯하다가도 안풀렸다. 이 글을 정리하며 어느정도 다시 개념을 다 잡았으니 시간날 때마다 문제를 다시 풀어봐야겠다. 특히 탐색하는 문제가 많았으니 탐색을 좀 더 신경써서 봐야겠다. 또, 삭제하는 코드도 이해가 잘 안되니 좀 더 볼 수 있도록 해야겠다. 꼭 디버깅을 한번 돌려보자. 이해가 바로 되는 것이 신기하다. 이제 구현만 할 줄알면.. 시간이 너무 부족한게 아쉽다..