thenullpage.com
1. 값을 아무 자리에나 놓지 않기로 약속하면
이진 트리는 자식을 최대 둘까지 둔다는 모양만 정할 뿐 값이 어디에 놓이든 상관하지 않습니다. 규칙을 하나 얹어 보겠습니다. 어떤 노드의 왼쪽 아래에는 그보다 작은 값만, 오른쪽 아래에는 큰 값만 놓는 규칙입니다. 이 조건을 지키는 트리가 이진 탐색 트리(binary search tree), 줄여서 BST입니다.
바로 아래 자식 둘만 보는 규칙이 아닙니다. 왼쪽 서브트리 전체가 기준값보다 작고 오른쪽 서브트리 전체가 커야 합니다. 대가로 얻는 것은 속도이며, 값을 찾을 때 한쪽 가지를 통째로 건너뛸 수 있습니다.
2. 넣을 자리는 트리가 알려줍니다
BST에서는 넣을 자리를 사람이 고르지 않습니다. 루트부터 작으면 왼쪽, 크면 오른쪽으로 내려가다 빈자리를 만나면 그곳이 자리입니다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
tree = None
for v in [50, 30, 70, 20, 40, 60, 80]:
tree = insert(tree, v)
print(tree.value, tree.left.value, tree.right.value)
50 30 70
insert가 노드를 돌려주고 부모가 그것을 자기 자리에 다시 붙이는 모양입니다. 빈자리에서는 새 노드를, 아니면 자기 자신을 돌려줍니다. 덕분에 트리가 비어 있는 첫 삽입도 같은 코드로 처리되고, 값이 같으면 두 조건 어디에도 걸리지 않아 그냥 지나갑니다.
3. 탐색은 한쪽을 통째로 버립니다
찾는 값과 현재 노드를 비교하면 갈 방향이 정해집니다. 작으면 왼쪽, 크면 오른쪽이라 반대쪽은 볼 필요가 없습니다.
def search(node, value):
steps = 0
while node is not None:
steps += 1
if value == node.value:
return steps
node = node.left if value < node.value else node.right
return -1
print(search(tree, 60))
print(search(tree, 45))
3
-1
60은 세 번 비교해서 찾았고 45는 트리에 없어서 -1이 나왔습니다. 세 번으로 끝난 것은 50과 비교하는 순간 왼쪽의 20, 30, 40이 한꺼번에 후보에서 빠졌기 때문입니다. 왼쪽으로만 계속 내려가 더 갈 곳이 없는 노드가 최솟값이고 오른쪽 끝이 최댓값입니다.
4. 정렬된 값을 넣으면 트리가 무너집니다
여기까지만 보면 BST는 늘 빠를 것 같지만, 값이 들어오는 순서에 따라 모양이 달라집니다.
def levels(node):
if node is None:
return 0
return 1 + max(levels(node.left), levels(node.right))
skewed = None
for v in [20, 30, 40, 50, 60, 70, 80]:
skewed = insert(skewed, v)
print(levels(tree), levels(skewed))
print(search(tree, 80), search(skewed, 80))
3 7
3 7
담긴 값은 똑같이 일곱 개인데 층수가 3과 7이고 80을 찾는 비교 횟수도 3과 7입니다. 오름차순으로 넣으면 새 값이 늘 커서 오른쪽으로만 붙어, 왼쪽 자식이 하나도 없는 한 줄짜리 트리가 됩니다. 사실상 연결 리스트입니다.
그래서 BST의 비용은 O(log n)이 아니라 층수에 비례한다고 해야 정확합니다. 잘 퍼졌을 때가 O(log n)이고 최악은 O(n)입니다. 정렬된 데이터를 그대로 넣는 일이 드물지 않아, 넣을 때마다 스스로 모양을 잡는 트리가 따로 필요합니다.
5. 삭제는 세 가지 경우로 나뉩니다
삭제는 지운 자리를 아무 값으로나 메우면 순서 규칙이 깨지기 때문에 BST에서 가장 손이 많이 가는 연산입니다. 자식이 없으면 그냥 떼어 내고, 하나면 그 자식을 자기 자리로 올립니다. 자식이 둘이면 오른쪽 서브트리의 최솟값을 데려옵니다. 지울 노드보다는 크고 오른쪽의 어떤 값보다도 작아 그 자리에 앉아도 규칙이 유지됩니다.
def delete(node, value):
if node is None:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
succ = node.right
while succ.left:
succ = succ.left
node.value = succ.value
node.right = delete(node.right, succ.value)
return node
tree = delete(tree, 20)
tree = delete(tree, 70)
print(tree.left.left, tree.right.value, tree.right.left.value)
None 80 60
자식이 없는 20은 None이 부모의 왼쪽 칸에 돌아가 사라집니다. 자식이 둘인 70은 최솟값 80으로 자기 값을 덮어쓴 뒤 원래 있던 80을 지웁니다. 값만 복사하고 원본을 남기면 같은 값이 두 개가 되므로 delete를 다시 부르는데, 그 노드는 왼쪽 자식이 없어 앞의 두 경우에서 끝납니다.
6. 유효성 검사에서 자주 나오는 실수
BST인지 검사할 때 노드를 자기 자식하고만 비교하는 코드를 자주 보게 되는데, 아래 bad가 그런 코드를 통과합니다.
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.value < high):
return False
return is_bst(node.left, low, node.value) and is_bst(node.right, node.value, high)
bad = Node(10)
bad.left = Node(5)
bad.right = Node(20)
bad.right.left = Node(8)
print(is_bst(tree), is_bst(bad))
True False
8은 부모인 20보다 작아 자식끼리만 보면 멀쩡해 보이지만, 루트 10의 오른쪽에 있으므로 10보다 커야 합니다. 위 코드는 내려가면서 허용 범위인 low와 high를 같이 넘겨 이런 경우를 잡습니다. 오른쪽으로 갈 때는 하한을, 왼쪽으로 갈 때는 상한을 자기 값으로 바꿉니다.
7. 챙길 것
BST는 순서 규칙 하나로 후보를 한쪽씩 덜어 내는 구조입니다.
기억할 것은 세 가지입니다. 순서 조건은 자식이 아니라 서브트리 전체에 걸린다는 것, 비용은 노드 수가 아니라 층수에 비례한다는 것, 정렬된 순서로 넣으면 층수가 노드 수만큼 커져 이점이 사라진다는 것입니다.