1. 이진탐색트리(Binary Search Tree; BST)란?
■ 이진탐색트리는 탐색에 이진트리 구조를 이용한 효율적인 탐색을 위한 자료구조이다.
■ 이진탐색트리의 삽입, 삭제, 탐색의 시간 복잡도는 모두 \( O(\log_2 n) \) 즉, \( O(\log_n) \)으로 이루어진다.
■ 효율적인 탐색 작업을 하기 위한 이진탐색트리는 다음과 같이 재귀적으로 정의된다.
- (1) 모든 노드는 유일한 키(= 서로 다른 키)를 갖는다.
- (2) 왼쪽 서브트리의 키(key)들은 루트의 키보다 작다.
- (3) 오른쪽 서브트리의 키들은 루트의 키보다 크다.
\( \rightarrow \) (2)와 (3)을 통해 알 수 있는 것은 이진탐색트리는 '왼쪽 서브트리 노드의 키값 < 루트 노드의 키값 < 오른쪽 서브트리의 키값'이다.
- (4) 왼쪽과 오른쪽 서브트리도 이진탐색트리이다. \( \rightarrow \) 이진탐색트리는 재귀적인 구조를 갖는다.
■ 정리하자면, 이진탐색트리의 모든 노드는 서로 다른 키를 가지면서, '왼쪽 서브트리 노드의 키값 < 루트 노드의 키값 < 오른쪽 서브트리의 키값'을 만족한다. 또한, 왼쪽과 오른쪽 서브트리도 이진탐색트리이므로 왼쪽 서브트리와 오른쪽 서브트리도 모든 노드는 서로 다른 키를 가지면서 '왼쪽 서브트리 노드의 키값 < 루트 노드의 키값 < 오른쪽 서브트리의 키값'을 만족한다.
■ 예를 들어 다음과 같은 트리는 이진탐색트리의 정의를 만족한다.
예를 들어 다음 트리는 이진탐색트리일까 아닐까? 정답은 아니다. 이다.
8이 루트 노드일 때, 루트 노드 8의 오른쪽 서브트리의 킷값은 루트 노드의 킷값 8보다 커야하기 때문에 '7'이 올 수 없기 때문이다.
■ 먼저 전체 트리는 모든 노드가 유일한 값을 가지며, 왼쪽 서브트리 노드의 키값(6, 3, 13) < 루트 노드의 키값(18) < 오른쪽 서브트리 노드의 키값(26, 32, 29)을 만족한다.
- 노드 '18'의 왼쪽 서브트리도 3 < 6 < 13으로 이진탐색트리의 정의를 만족한다.
- 노드 '18'의 오른쪽 서브트리도 ∅ (공백 노드) < 26 < 32 & 26 < 32 < ∅ (공백노드) 로 이진탐색트리의 정의를 만족한다.
따라서 예시의 트리는 이진탐색트리이다.
■ 예시의 이진탐색트리를 중위 순회하면 3, 6, 13, 19, 26, 29, 32로 오름차순 정렬된다. 따라서 이진탐색트리는 어느 정도 정렬된 상태를 유지하는 것으로 볼 수 있다.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.data, end = ' ')
inorder(node.right)
node_G = TreeNode('29', None, None)
node_F = TreeNode('32', node_G, None)
node_E = TreeNode('13', None, None)
node_D = TreeNode('3', None, None)
node_C = TreeNode('26', None, node_F)
node_B = TreeNode('6', node_D, node_E)
root_node = TreeNode('19', node_B, node_C)
inorder(root_node)
```#결과#```
3 6 13 19 26 29 32
```````````
2. 이진탐색트리의 연산
■ 이진탐색트리는 이진트리의 한 종류라서 공백 검사,, 순회 방법 등 기본적인 이진트리 연산은 이진탐색트리에도 동일하게 적용된다. 즉, 노드의 구조는 기본적으로 이진트리와 동일하다.
■ 단, 이진'탐색'트리이므로 이 트리의 목적은 탐색에 중점을 둔다. 또한 삽입, 삭제 연산 후에도 이진탐색트리의 정의를 만족해야 하므로 이진탐색트리의 탐색, 삽입, 삭제 연산은 노드의 키 값 비교를 기반으로 재귀적으로 구현해야 한다.
■ 또한, 탐색을 위한 자료구조이므로 노드의 데이터는 하나의 엔트리(탐색키 - 키에 대한 값)로 구성되어야 한다.
■ 이를 고려하면 이진탐색트리 노드 클래스는 다음과 같이 구현할 수 있다.
class BSTNode:
def __init__(self, key, value, left = None, right = None):
self.key = key
self.value = value
self.left = left # 왼쪽 자식 노드
self.right = right # 오른쪽 자식 노드
# def __repr__(self):
# return f'BSTNode(key={self.key}, value={self.value})'
2.1 탐색 연산 - (1) 키를 이용한 탐색
■ 키를 이용한 탐색은 항상 루트 노드에서 시작하며, 루트 노드와의 비교 결과는 3가지 중 하나이다.
- 찾고자 하는 key 값이 \( k \)이면, 루트 노드에 저장된 key 값과 \( k \)를 비교해서
- ① \( k \) == 루트 노드의 키 값 : 루트 노드가 찾고자 하는 노드
- ② \( k \) < 루트 노드의 키 값 : 이진탐색트리 특성( 왼쪽 서브트리 노드의 키값 < 루트 노드의 키값 < 오른쪽 서브트리의 키값)에 따라 \( k \)는 왼쪽 서브트리에 있다. 따라서 왼쪽 서브트리의 루트 노드를 기준으로 다시 탐색을 시작한다.
- ③ \( k \) > 루트 노드의 키 값 : 이진탐색트리 특성( 왼쪽 서브트리 노드의 키값 < 루트 노드의 키값 < 오른쪽 서브트리의 키값)에 따라 \( k \)는 오른쪽 서브트리에 있다. 따라서 오른쪽 서브트리의 루트 노드를 기준으로 다시 탐색을 시작한다.
■ 키를 이용해 탐색할 경우 이렇게 재귀적인 구조를 가지므로 순환 호출로 구현하는 것이 적합하며, 반복 구조로도 구현할 수 있다. 효율성만 따진다면, 반복 구조가 더 우수하다.
■ 예를 들어 위의 예시 트리에서 '13'을 탐색한다면
- 1) 먼저 루트 노드와 비교한다. \( k \) = 13 < 19이므로 찾고자 하는 값은 왼쪽 서브트리에 있다.
- 2) 왼쪽 서브트리의 루트 노드와 비교한다. 13 > 7이므로 찾고자 하는 값은 오른쪽 서브트리에 있다. 오른쪽 서브트리로 이동한다.
- 3) 오른쪽 서브트리의 루트 노드와 비교한다. 13 == 13이므로 찾고자 하는 탐색 키와 동일하다. 탐색 성공.
■ 반면, 트리에 없는 '33'을 탐색한다면, 비교를 통해 노드 '33'의 오른쪽 서브트리로 이동해야 하지만 노드 '32'는 오른쪽 자식 노드가 없어서 더 이상 탐색을 진행할 수 없다. 탐색 실패.
# 탐색 연산 - 키를 이용한 탐색 - 순환 구조
def search(root, key):
if root == None:
return None
elif key == root.key:
return root
elif key < root.key:
return search(root.left, key)
else:
return search(root.right, key)
# 탐색 연산 - 키를 이용한 탐색 - 반복 구조
def search_iter(root, key):
while root != None: # 루트 노드가 None이 아닐 때까지
if key == root.key:
return root
elif key < root.key:
root = root.left
else:
root = root.right
return Noneroot = BSTNode(19, 'A')
root.left = BSTNode(6, 'B')
root.right = BSTNode(26, 'C')
root.left.left = BSTNode(3, 'D')
root.left.right = BSTNode(13, 'E')
root.right.right = BSTNode(32, 'F')
root.right.right.left = BSTNode(29, 'G')
for i in [19, 6, 26, 3, 13, 32, 29]:
print(search(root, i))
print(search(root, 33))
```#결과#```
BSTNode(key=19, value=A)
BSTNode(key=6, value=B)
BSTNode(key=26, value=C)
BSTNode(key=3, value=D)
BSTNode(key=13, value=E)
BSTNode(key=32, value=F)
BSTNode(key=29, value=G)
None # 탐색 실패
``````````````
print(search_iter(root, 14)); print(search_iter(root, 29))
```#결과#```
None
BSTNode(key=29, value=G)
`````````````■ 위의 예에서 탐색 성공이든 탐색 실패이든 트리의 전체 노드 중 일부 노드만 검사하고 탐색을 수행했다. 이런 효율적인 탐색을 하기 위해서는 트리가 반드시 이진탐색트리의 정의를 충족시키는 형태로 구성되어 있어야 한다.
2.2 탐색 연산 - (2) 값을 이용한 탐색
■ 이진탐색트리는 엔트리의 값을 이용해 탐색 연산을 수행할 수도 있다.
■ 단, 전위 순회를 이용하여 찾고자 하는 값이 트리에 없는 경우 키를 이용해 탐색하는 방법과 달리 모든 노드를 검사해야 한다. 즉 시간 복잡도는 \( O(n) \)이다.
# 탐색 연산 - 값을 이용한 탐색
def search_value(root, value):
if root == None:
return None
elif value == root.value:
return root
node = search_value(root.left, value) # 왼쪽 서브트리 탐색
if node is not None: # 탐색 성공이면
return node
else: # 탐색 실패면
return search_value(root.right, value) # 오른쪽 서브트리 탐색root = BSTNode('A', 19)
root.left = BSTNode('B', 6)
root.right = BSTNode('C', 26)
root.left.left = BSTNode('D', 3)
root.left.right = BSTNode('E', 13)
root.right.right = BSTNode('F', 32)
root.right.right.left = BSTNode('G', 29)
for i in [19, 6, 26, 3, 13, 32, 29]:
print(search_value(root, i))
print(search_value(root, 'H'))
```#결과#```
BSTNode(key=A, value=19)
BSTNode(key=B, value=6)
BSTNode(key=C, value=26)
BSTNode(key=D, value=3)
BSTNode(key=E, value=13)
BSTNode(key=F, value=32)
BSTNode(key=G, value=29)
None # 탐색 실패
````````````
2.3 탐색 연산 - 최대 & 최소 노드 탐색
■ 이진탐색트리는 어느 정도 정렬된 상태를 유지하기 때문에 최대 키, 최소 키를 가진 노드를 찾는 연산이 비교적 쉬운 편에 속한다.
■ 이진트리의 특성상, 최대 키는 트리의 가장 오른쪽 노드에, 최소 키는 트리의 가장 왼쪽에 있다.
■ 최소 키는 루트 노드에서 시작하여 더 이상 왼쪽으로 갈 수 없을 때까지 계속해서 왼쪽으로 이동하도록 구현하면 된다. 최대 키도 루트 노드에서 시작하여 더 이상 오른쪽으로 갈 수 없을 때까지 계속해서 오른쪽으로 이동하도록 구현하면 된다.
- 위의 '33'을 찾는 탐색 실패를 생각해 보면, 비록 이진탐색트리의 노드는 아니었지만, 예시의 이진탐색트리의 전체 노드 중 가장 큰 값이었기 때문에, 이진탐색트리의 크기 조건 특성에 따라 탐색 과정에서 계속 오른쪽 서브트리로 이동하였다.
# 탐색 연산 - 최소 키, 최대 키 탐색
## 반복 구조
### 최소 키
def search_min_key(root):
while root != None and root.left != None:
root = root.left
return root
### 최대 키
def search_max_key(root):
while root != None and root.right != None:
root = root.right
return root
root = BSTNode(19, 'A')
root.left = BSTNode(6, 'B')
root.right = BSTNode(26, 'C')
root.left.left = BSTNode(3, 'D')
root.left.right = BSTNode(13, 'E')
root.right.right = BSTNode(32, 'F')
root.right.right.left = BSTNode(29, 'G')
print(search_min_key(root)); print(search_max_key(root));
```#결과#```
BSTNode(key=3, value=D)
BSTNode(key=32, value=F)
````````````- 다음과 같이 순환 구조로도 구현할 수 있다.
## 순환 구조
### 최소 키
def search_min_key_recursive(root):
if root is None: # 루트 노드가 비어있으면
return None # None 반환
if root.left is None: # 루트 노드의 왼쪽이 비어있으면
return root # 현재 노드가 최소 키를 가진 노드
return search_min_key_recursive(root.left) # 왼쪽 자식이 존재하면 재귀 호출로 계속 탐색
### 최대 키
def search_max_key_recursive(root):
if root is None: # 루트 노드가 비어있으면
return None # None 반환
if root.right is None: # 루트 노드의 오른쪽이 비어있으면
return root # 현재 노드가 최대 키를 가진 노드
return search_max_key_recursive(root.right) # 오른쪽 자식이 존재하면 재귀 호출로 계속 탐색
print(search_min_key_recursive(root)); print(search_max_key_recursive(root))
```#결과#```
BSTNode(key=3, value=D)
BSTNode(key=32, value=F)
````````````
2.4 삽입 연산
■ 삽입 연산은 삽입할 노드의 키를 이용한 탐색을 수행해야 한다. 탐색에 실패해 탐색이 종료된 위치가 새로운 노드를 삽입해야 하는 위치이기 때문이다. 그리고 삽입 후에도 트리가 이진탐색트리의 정의를 만족해야 한다.
■ 위의 '33' 탐색 실패 예시에서 '33' 탐색 시 '33'이 위치할 곳으로 이동했던 과정을 생각해 보면 된다.
■ 이번에는 '33'을 삽입한다면
■ 삽입 연산에서 주의할 점은 삽입 위치는 탐색에 실패한 위치이므로 중복된 키를 가진 노드가 이미 이진탐색트리에 존재한다면, 탐색에 성공해 삽입 위치를 결정하기 어렵다는 점이 있다.
■ 따라서 삽입 연산은 키의 중복을 허용하지 않는다.
def insert(root_node, new_node):
if new_node.key < root_node.key: # 삽입 노드의 key < 루트 노드의 key 일 때
if root_node.left is None: # 루트 노드의 왼쪽이 없으면 (= 탐색 실패이면)
root_node.left = new_node # 루트 노드의 왼쪽 자식은 새로운 노드가 된다.(= 삽입 성공)
return True
else: # 루트 노드의 왼쪽이 있으면
return insert(root_node.left, new_node) # 루트 노드의 왼쪽 (서브트리)부터 다시 삽입 연산을 시작한다.
elif new_node.key > root_node.key: # 삽입 노드의 key > 루트 노드의 key 일 때
if root_node.right is None: # 루트 노드의 오른쪽이 없으면 (= 탐색 실패이면)
root_node.right = new_node # 루트 노드의 오른쪽 자식은 새로운 노드가 된다.(= 삽입 성공)
return True
else: # 루트 노드의 오른쪽이 있으면
return insert(root_node.right, new_node) # 루트 노드의 오른쪽 (서브트리)부터 다시 삽입 연산을 시작한다.
else: # 키가 중복되면
# print(f'키 {new_node.key}은/는 이미 트리에 존재.')
return False # 삽입하지 않는다.root = BSTNode(19, 19)
root.left = BSTNode(6, 6)
root.right = BSTNode(26, 26)
root.left.left = BSTNode(3, 3)
root.left.right = BSTNode(13, 13)
root.right.right = BSTNode(32, 32)
root.right.right.left = BSTNode(29, 29)
for i in [19, 6, 26, 3, 13, 32, 29]:
print(search(root, i))
print(search(root, 33))
```#결과#```
BSTNode(key=19, value=19)
BSTNode(key=6, value=6)
BSTNode(key=26, value=26)
BSTNode(key=3, value=3)
BSTNode(key=13, value=13)
BSTNode(key=32, value=32)
BSTNode(key=29, value=29)
None
`````````````
new = BSTNode(33, 33)
insert(root, new)
print(search(root, 33)); print(search_max_key_recursive(root));
```#결과#```
BSTNode(key=33, value=33)
BSTNode(key=33, value=33)
`````````````
2.5 삭제 연산
■ 이진탐색트리는 노드 삭제 후에도 이진탐색트리의 정의를 만족해야 한다. 이러한 특성 때문에 삭제 연산은 3가지 경우로 나누어진다.
- ① 삭제하려는 노드가 리프 노드일 경우(= 자식 노드의 수가 0개인 경우)
- ② 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 하나만 가지고 있는 경우(= 자식 노드의 수가 1개인 경우)
- ③ 삭제하려는 노드가 왼쪽, 오른쪽 서브트리 모두 가지고 있는 경우(= 자식 노드의 수가 2개인 경우)
2.5.1 삭제 연산 - 삭제하려는 노드가 리프 노드일 경우
■ 이 경우는 삭제하려는 리프 노드만 삭제하면 되서 가장 간단한 경우이다. 리프 노드를 삭제해도 이진탐색트리의 정의가 유지되기 때문이다.
■ 예를 들어 다음과 같은 이진탐색트리에서 리프 노드 '15'를 삭제해도 이진탐색트리가 유지되는 것을 볼 수 있다.
■ 리프 노드를 삭제하는 방법은 해당 리프 노드의 부모 노드의 자식(= 리프 노드)을 None으로 변경하면 된다.
- 예를 들어 '28'을 삭제하려면 그 부모 노드인 '24'의 오른쪽 자식을 None으로 변경,
- '10'을 삭제하려면 그 부모 노드인 '12'의 왼쪽 자식을 None으로 변경하면 된다.
def delete_leaf_node(root_node, parent_node, delete_node):
if parent_node is None: return None
else:
if parent_node.left == delete_node: # 삭제하려는 노드가 부모의 왼쪽 자식이면
parent_node.left = None # 부모 왼쪽 자식을 None으로 변경
else: # 삭제하려는 노드가 부모의 오른쪽 자식이면
parent_node.right = None # 부모 오른쪽 자식을 None으로 변경
return root_node # 삭제하려는 리프 노드가 루트 노드인 경우 루트 노드는 None으로 변경되기 때문에 root_node를 반환하여 트리의 최신 상태를 확인한다.# 루트 노드 1개만 있는 경우
root2 = BSTNode(16, 'A')
print(delete_leaf_node(root2, None, root2)) # 부모 노드가 없다 = 자식이 없는 루트 노드 1개 = 리프 노드
```#결과#```
None
````````````root2 = BSTNode(16, 16)
root2.left = BSTNode(8, 8)
root2.right = BSTNode(24, 24)
root2.left.left = BSTNode(4, 4)
root2.left.right = BSTNode(12, 12)
root2.right.left = BSTNode(20, 20)
root2.right.right = BSTNode(28, 28)
root2.left.left.left = BSTNode(2, 2)
root2.left.left.right = BSTNode(5, 5)
root2.left.right.left = BSTNode(10, 10)
root2.left.right.right = BSTNode(15, 15)
delete_leaf_node(root2, root2.left.right, root2.left.right.right) # (root, 12, 15)
print(search(root2, 15))
```#결과#```
None
````````````
2.5.2 삭제 연산 - 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 하나만 가지고 있는 경우
■ 자식을 하나만 가지는 노드를 삭제할 경우, 삭제한 노드의 자식 노드를 삭제한 노드의 부모와 연결시켜주면 된다. 삭제한 노드의 자식이 서브트리의 루트 노드라고 해도 그 서브트리도 이진탐색트리이기 때문에 문제 될 것이 없다.
■ 자식이 하나인 노드 삭제 시, 삭제할 노드를 A라 하자. 삭제 후에는 A의 부모와 A의 자식을 연결시켜줘야 한다.
■ 연결 방법은 A가 A 부모의 오른쪽 자식이었다면, A의 자식을 A 부모의 새로운 오른쪽 자식으로 연결, A가 A 부모의 왼쪽 자식이었다면, A의 자식을 A 부모의 새로운 왼쪽 자식으로 연결하면 된다.
■ 단, 연결하기 전에 A는 왼쪽 또는 오른쪽 자식 하나만 가지므로 A의 자식이 왼쪽에 있는지 오른쪽에 있는지를 먼저 확인해야 한다.
def delete_one_child_node(root_node, parent_node, delete_node):
# 자식 노드가 하나라는 가정 하에
if delete_node.left is not None: # 삭제할 노드가 왼쪽 자식이 있으면
child = delete_node.left # 삭제할 노드의 자식은 왼쪽 자식이고
else: # 삭제할 노드가 오른쪽 자식이 있으면
child = delete_node.right # 삭제할 노드의 자식은 오른쪽 자식이다.
if delete_node == root_node: # 삭제할 노드가 루트 노드이면
root_node = child # child가 새로운 루트 노드가 된다.
else:
if delete_node is parent_node.left: # 삭제할 노드가 삭제할 노드의 부모 노드 왼쪽 자식이라면
parent_node.left = child # 삭제할 노드의 (왼쪽) 자식을, 삭제할 노드의 부모 자식과 연결
else: # 삭제할 노드가 삭제할 노드의 부모 노드 오른쪽 자식이라면
parent_node.right = child # 삭제할 노드의 (오른쪽) 자식을, 삭제할 노드의 부모 자식과 연결
return root_nodedelete_one_child_node(root2, root2.left, root2.left.right)
print(search(root2, 12))
```#결과#```
None
````````````
2.5.3 삭제 연산 - 삭제하려는 노드가 왼쪽, 오른쪽 서브트리 모두 가지고 있는 경우
■ 이 경우에도 삭제 후, 이진탐색트리를 만족해야 한다.
■ 트리의 구조를 최대한 바꾸지 않는 방향에서 삭제할 노드의 대체 노드는 이진탐색트리의 크기 조건을 유지할 수 있도록 삭제할 노드와 킷값이 비슷한 노드일수록 좋다.
■ 예를 들어 다음과 같은 트리에서 두 개의 자식 노드를 모두 가지는 '8'을 삭제한다면,
노드 '8'을 대체할 노드를 찾아야 한다.
- 이진탐색트리의 조건을 유지시킬 수 있으면서 '8'과 킷값이 비슷한 노드는 노드 '8'의 '왼쪽 서브트리에서 가장 큰 값(5)'과 '오른쪽 서브트리에서 가장 작은 값(10)'이다.
- 두 값은 삭제할 노드와 가장 가까운 작은 값, 큰 값이다. 따라서 삭제 위치에 들어가도 왼쪽 서브트리 노드의 킷값보다 크고 오른쪽 서브트리 노드의 킷값보다 작은 조건을 충족시킬 수 있다. 따라서 두 노드 '5', '10' 중 대체 노드로 어떤 것을 선택해도 상관없다.
- 단, 이 후보군의 자식 노드는 반드시 1개 이하여야 한다.
- 만약, '10'을 대체 노드로 선택한다면, 먼저 대체 노드 '10'을 찾기 위해 최대/최소 키 탐색 방법을 이용해 '8'의 오른쪽 서브트리에서 가장 작은 값을 찾으면 된다. 최대/최소 키 탐색을 이용하기 때문에 대체 노드의 자식 노드 수가 반드시 1개 이하여야 한다는 것이다.
- 이 예에서는 최소 키 탐색을 이용해야 하므로 '10'이 '8'의 오른쪽 서브트리의 가장 작은 값이 되기 위해선 '10'의 왼쪽 자식 노드는 없어야 한다.(= None 이어야 한다.)
- 이때, '10'의 왼쪽 자식은 없지만, 오른쪽 자식 노드는 존재할 수 있다. '10'이 왼쪽, 오른쪽 자식이 모두 없다면 '10'을 삭제할 '8'의 위치에 바로 올리면 된다.
- 만약, '10'이 오른쪽 서브트리(자식 노드)가 있다면, 이 서브트리는 '10'보다 큰 값, '12'보다 작은 값이므로 '10'이 삭제 위치 '8'로 이동할 때, '10'의 오른쪽 서브트리가 '12'의 왼쪽 자식으로 연결되어야 이진탐색트리의 조건을 만족할 수 있다.
■ 두 개의 노드를 자식으로 갖는 노드 '8'의 삭제 예시를 들어 과정을 순서대로 나타내면
- ① 삭제할 노드의 대체 노드를 '8'의 왼쪽, 오른쪽 서브트리에 최대/최소 키 탐색을 이용하여 찾는다. 이때, 최대/최소 키 탐색을 이용하므로 대체 노드의 자식 노드의 수는 1개 이하여야 한다.
- ② 대체 노드의 자식 노드가 아예 없다면, 대체 노드의 엔트리(키-값)를 삭제할 노드에 복사하면 된다. 만약, 대체 노드의 자식 노드가 있다면 대체 노드는 삭제 위치로 이동하기 때문에 대체 노드의 부모 노드와 대체 노드의 자식 노드를 연결해야 한다. 그리고 대체 노드의 엔트리를 삭제할 노드에 복사하면 된다.
def delete_two_child_node(root_node, delete_node):
# 초기화 # 대체 노드 찾기 (오른쪽 서브트리의 최소 노드)
replace_parent = delete_node
replace = delete_node.right
# print(f'시작: {replace_parent}, {replace}')
while replace.left:
replace_parent = replace
replace = replace.left
# print(f'replace_parent, replace: {replace_parent}, {replace}\n')
# 대체 노드의 부모 노드와 대체 노드의 자식 노드를 연결
if replace_parent.left == replace:
replace_parent.left = replace.right
else:
replace_parent.right = replace.right
# 삭제할 노드의 키-값을 대체 노드의 키-값으로 대체
delete_node.key, delete_node.value = replace.key, replace.valueroot3 = BSTNode(16, 16)
root3.left = BSTNode(8, 8)
root3.right = BSTNode(24, 24)
root3.left.left = BSTNode(4, 4)
root3.left.right = BSTNode(12, 12)
root3.right.left = BSTNode(20, 20)
root3.right.right = BSTNode(28, 28)
root3.left.left.left = BSTNode(2, 2)
root3.left.left.right = BSTNode(5, 5)
root3.left.right.left = BSTNode(10, 10)
root3.left.right.right = BSTNode(15, 15)
root3.left.right.left.right = BSTNode(11, 11)
def revise_search_min_key(root):
parent = None
current = root
while current != None and current.left != None:
parent = current # 최소 키 직전의 노드(= 부모 노드)
current = current.left # 최소 키
return (parent, current)
def revise_search_max_key(root):
parent = None
current = root
while current != None and current.right != None:
parent = current # 최대 키 직전의 노드(= 부모 노드)
current = current.right # 최대 키
return (parent, current)
revise_search_max_key(root3.left.left) # 노드 '8'의 왼쪽 서브트리에서의 최대 키
```#결과#```
(BSTNode(key=4, value=4), BSTNode(key=5, value=5))
````````````
revise_search_min_key(root3.left.right) # 노드 '8'의 오른쪽 서브트리에서의 최소 키
```#결과#```
(BSTNode(key=12, value=12), BSTNode(key=10, value=10))
````````````delete_two_child_node(root3, root3.left)
```#결과#```
시작: BSTNode(key=8, value=8), BSTNode(key=12, value=12)
replace_parent, replace: BSTNode(key=12, value=12), BSTNode(key=10, value=10)
````````````
## 모든 경우에 대한 삭제 연산
def delete(root_node, key):
if root_node is None: return None # 공백 트리
# 초기화 # 키를 이용해 삭제할 노드를 찾아가는 과정
parent_node, delete_node = None, root_node
while delete_node is not None and delete_node.key != key:
parent_node = delete_node
if key < delete_node.key:
delete_node = delete_node.left
else:
delete_node = delete_node.right
if delete_node is None: return None # 삭제할 노드가 없는 경우
if delete_node.left == None and delete_node.right == None: # 리프 노드 삭제인 경우
root_node = delete_leaf_node(root_node, parent_node, delete_node)
elif delete_node.left == None or delete_node.right == None: # 하나의 자식만 가지는 노드 삭제인 경우
root_node = delete_one_child_node(root_node, parent_node, delete_node)
else: # 두 개의 자식을 가지는 노드 삭제인 경우
root_node = delete_two_child_node(root_node, delete_node)
return root_node
3. 이진탐색트리를 이용한 맵
■ 생성자 메서드 부분에는 루트 노드를 가리킬 변수만 있으면 된다. 키는 각 이진탐색트리 메서드 별로 받아 사용하면 되고, 삽입 연산을 통해 루트 노드를 새롭게 설정하면 되기 때문이다.
class BSTMap:
def __init__(self):
self.root = None # 트리 루트 노드■ 생성자 메서드를 위와 같이 설정하면 공백 검사는 root == None 인지 확인하면 되고, 초기화는 root를 None으로 만들면 된다. 그리고 트리의 사이즈는 노드 개수를 세는 함수를 호출하면 된다.
def BSTMapIsEmpty(self): return self.root == None
def BSTMapClear(self): self.root = None
def BSTMapSize(self): return count_node(self.root)def count_node(node):
if node is None: # node is None이면 공백 트리이므로
return 0 # 노드 개수는 0
else:
return 1 + count_node(node.left) + count_node(node.right)
■ 삽입 연산은 BSTNode 클래스로 새로운 노드를 만들어서, 초기 트리가 공백이면 생성한 노드를 루트 노드로 설정하고, 공백 트리가 아니면 insert( ) 함수를 호출해 삽입하면 된다.
def BSTMapInsert(self, key, value):
node = BSTNode(key, value) # 새로운 노드 생성
if self.BSTMapIsEmpty(): # 공백 트리이면
self.root = node # 새로 생성한 노드를 루트 노드로 설정
else: # 공백이 아니면
insert(self.root, node) # 일반적인 삽입■ 나머지 탐색, 최대/최소 키 탐색, 삭제 연산은 위에서 구현한 함수들을 호출해서 사용하면 된다. 단, 탐색과 삭제 연산은 키가 필요하므로 킷값을 따로 입력받아야 한다.
def BSTMapSearch(self, key): return search(self.root, key)
def BSTMapSearchMaxKey(self, key): return search_max_key(self.root, key)
def BSTMapSearchMinKey(self, key): return search_min_key(self.root, key)
def BSTMapDelete(self, key): return delete(self.root, key)■ 이 외에 inorder( )를 호출해서 트리를 출력한다.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.key, end = ' ')
inorder(node.right)
def BSTMapDisplay(self):
print(inorder(self.root))# 이진탐색트리 맵
class BSTMap:
def __init__(self):
self.root = None # 트리 루트 노드
def BSTMapIsEmpty(self): return self.root == None
def BSTMapClear(self): self.root = None
def BSTMapSize(self): return count_node(self.root)
def BSTMapInsert(self, key, value):
node = BSTNode(key, value) # 새로운 노드 생성
if self.BSTMapIsEmpty(): # 공백 트리이면
self.root = node # 새로 생성한 노드를 루트 노드로 설정
else: # 공백이 아니면
insert(self.root, node) # 일반적인 삽입
def BSTMapSearch(self, key): return search(self.root, key)
def BSTMapSearchMaxKey(self, key): return search_max_key(self.root)
def BSTMapSearchMinKey(self, key): return search_min_key(self.root)
def BSTMapDelete(self, key): return delete(self.root, key)
def BSTMapDisplay(self):
inorder(self.root)bst_map = BSTMap()
for i in [16, 8, 24, 4, 12, 20, 28, 2, 5, 10, 15, 11]:
bst_map.BSTMapInsert(i, i)
print(bst_map.BSTMapIsEmpty()); print(bst_map.BSTMapSize())
```#결과#```
False
12
````````````
bst_map.BSTMapDisplay()
```#결과#```
2 4 5 8 10 11 12 15 16 20 24 28
````````````
print(bst_map.BSTMapSearch(10)); print(bst_map.BSTMapSearchMaxKey()); print(bst_map.BSTMapSearchMinKey())
```#결과#```
BSTNode(key=10, value=10)
BSTNode(key=28, value=28)
BSTNode(key=2, value=2)
````````````
bst_map.BSTMapDelete(11)
```#결과#```
BSTNode(key=16, value=16)
````````````
bst_map.BSTMapDisplay()
```#결과#```
2 4 5 8 10 12 15 16 20 24 28
````````````
bst_map.BSTMapClear()
print(bst_map.BSTMapIsEmpty()); print(bst_map.BSTMapSize())
```#결과#```
True
0
````````````
print(bst_map.BSTMapDisplay())
```#결과#```
None
````````````
4. 이진탐색트리의 성능
■ 탐색, 삽입, 삭제 연산의 시간은 트리의 높이에 비례한다.
■ 이진트리의 정의를 만족하는 한, 노드가 \( n \) 개일 때 극단적인 경우 높이 \( h = n \)인 경사 이진트리의 형태를 가질 수도 있기 때문이다. 따라서 최악의 경우 탐색, 삽입, 삭제 연산의 시간 복잡도는 \( O(n) \)이 된다.
■ 반대로 최선의 경우는 균형 트리인 포화이진트리의 형태로, 포화이진트리의 높이가 \( \log_2 n) \)이므로, 최선의 경우 탐색, 삽입, 삭제의 시간 복잡도는 \( O(\log_2 n) \)이 된다.
■ 따라서 트리의 높이를 \( \log_2 n) \)로 유지시키는 것이 중요하며, 이진탐색트리의 높이를 \( \log_2 n) \)으로 한정시키는 트리가 있는데, 이를 '균형이진탐색트리'라고 한다.
