이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 가질 수 있는 트리 구조
종류
- 완전 이진 트리(Complete Binary Tree): 모든 레벨이 꽉 차 있는 상태에서, 마지막 레벨을 제외하고 모든 노드가 채워져 있는 이진 트리 마지막 레벨은 왼쪽부터 채워진다.
- 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 꽉 차 있고, 모든 리프 노드가 같은 레벨에 있는 이진 트리
- 균형 이진 트리(Balanced Binary Tree): 어떤 노드의 두 자식 트리의 높이 차이가 최대 1인 이진 트리
이진 탐색 트리(Binary Search Tree, BST)
각 노드의 왼쪽 자식은 노드보다 작고, 오른쪽 자식은 노드보다 큰 값을 가지는 이진 트리
최선의 경우(이상적으로 균형 잡힌 트리)에는 트리의 높이가 $\log_2n$ 이므로, 탐색에 걸리는 시간 복잡도는 $O(\log n)$이 된다. 여기서 $n$은 트리의 노드 수다.
연산 설명 및 구현
직관적인 이해를 위해 리스트가 아닌 Node class를 정의하여 구현했다.
1
2
3
4
5
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
검색(Search)
루트부터 시작하여, 찾고자 하는 값과 노드의 값을 비교하며 탐색을 진행
1
2
3
4
5
6
7
# 이진 탐색 트리에서 검색 연산을 수행하는 함수
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)
삽입(Insertion)
삽입하고자 하는 값을 루트부터 시작하여 적절한 위치를 찾아 삽입
1
2
3
4
5
6
7
8
9
10
# 이진 탐색 트리에서 삽입 연산을 수행하는 함수
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
삭제(Deletion)
삭제하고자 하는 노드를 찾은 후, 노드의 자식 노드의 수에 따라 처리 방법이 달라진다.
자식 노드가 없는 경우(Leaf Node):
삭제하려는 노드가 리프 노드(자식 노드가 없는 노드)인 경우, 단순히 그 노드를 트리에서 제거하면 된다. 부모 노드의 해당 자식에 대한 참조를 None으로 설정한다.
한 개의 자식 노드만 있는 경우:
삭제하려는 노드가 한 개의 자식 노드만 가지고 있을 경우, 삭제되는 노드를 건너뛰고 그 자식 노드를 삭제되는 노드의 부모 노드에 직접 연결한다. 삭제하려는 노드의 부모 노드가 삭제하려는 노드 대신 삭제하려는 노드의 자식을 가리키도록 한다.
두 개의 자식 노드가 있는 경우:
삭제하려는 노드가 두 개의 자식 노드를 가지고 있는 경우, 좀 더 복잡한 처리가 필요하다. 이 경우, 삭제 노드를 대체할 새로운 노드를 찾아야 한다. 일반적으로 두 가지 방법 중 하나를 사용한다:
후계자 찾기(Successor):
삭제하려는 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드(후계자)를 찾는다. 이 후계자는 삭제하려는 노드를 대체하고, 후계자의 원래 위치는 후계자의 오른쪽 자식(있을 경우)이 대체한다.
선조 찾기(Predecessor):
삭제하려는 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드(선조)를 찾는다. 이 선조는 삭제하려는 노드를 대체하고, 선조의 원래 위치는 선조의 왼쪽 자식(있을 경우)이 대체한다.
후계자 또는 선조를 찾은 후, 해당 노드를 삭제하려는 노드의 위치로 이동시키고, 원래의 후계자 또는 선조의 위치에서 해당 노드를 제거한다. 이 과정에서 후계자 또는 선조의 자식 노드들도 적절히 재배치해야 할 수 있다.
이진 탐색 트리에서 노드를 삭제하는 과정은 트리의 구조를 유지하기 위해 세심한 주의가 필요하다. 특히, 두 개의 자식 노드를 가진 노드를 삭제할 때는 후계자나 선조를 찾는 과정이 중요하며, 이 과정을 통해 트리의 정렬 상태와 탐색 효율성을 보존할 수 있다.
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 minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
# 이진 탐색 트리에서 삭제 연산을 수행하는 함수
def deleteNode(root, key):
if root is None:
return root
if key < root.val:
root.left = deleteNode(root.left, key)
elif(key > root.val):
root.right = deleteNode(root.right, key)
else:
# 노드가 하나 또는 없는 경우
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
# 두 개의 자식 노드가 있는 경우
temp = minValueNode(root.right)
root.val = temp.val
root.right = deleteNode(root.right, temp.val)
return root