8. 이진 탐색 트리 (Binary Search Tree)

내부노드에 (키, 원소) 쌍을 저장하며, 아래 조건을 만족하는 적정 이진 트리를 이진 탐색 트리라 한다.

$u, v, w$가 모두 트리 노드이며, $u$와 $w$가 각각 $v$의 왼쪽과 오른쪽 부트리에 존재할 때, $\text{key}(u)<\text{key}(v)\leq \text{key}(w) $를 만족하는 경우.

때문에, 이진 탐색 트리를 중위 순회하면 키가 증가하는 순서로 방문할 수 있다.

탐색

키 $k$를 찾기 위해, 루트로부터 하향 경로로 탐색을 진행한다. 다음에 방문할 노드는 $k$와 현재 노드의 크기 비교를 통해 결정한다.

만약 탐색이 외부노드에 다다르면, 키 $k$가 발견되지 않았으므로 NoSuchKey 예외를 반환한다.

def findElem(k):
    v = treeSearch(root, k)
    if isExternal(v):
        raise Exception("NoSuchKey")
    return element(v)
def treeSearch(v, k):
    if isExternal(v): # 외부노드에 도달
        return v 
    if k == key(v): # 키 찾음
        return v
    if k < key(v): # 찾는 k 보다 v가 큼
        return treeSearch(v.left, k) # 더 작은 원소들이 있는 왼쪽 탐색
    if k > key(v): # 찾는 k 보다 v가 작음
        return treeSearch(v.right, k) # 더 큰 원소들이 있는 오른측 탐색

삽입

삽입에 앞서, 적절한 삽입 위치를 찾기위해 treeSearch로 $k$를 찾아준다. 당연히 $k$는 없겠지만, 이때 찾아진 위치에 외부 노드를 추가하여 삽입 위치로 쓰면 된다.

def insertItem(k, e):
    w = treeSearch(root(), k)
    if isInternal(w):
        raise Exception("Key Already Exists!")
    w.elem = e
    w.key = k
    w.expandExternal()
    return

삭제

삭제하고자 하는 원소의 자식 중 하나 이상이 외부 노드일 경우, reduceExternal을 통해 간단히 원소를 삭제할 수 있지만, 원소의 자식 모두가 내부 노드인 경우엔 조금 복잡하다.

삭제할 원소 w를 삭제하고, w의 중위순위 후계자를 복제하여 w를 대체하면 된다. (w는 자식 중 1개 이상이 외부노드이므로 그냥 지우면 된다.)

def removeElement(k):
    w = treeSearch(root(), k)
    if isExternal(w): # 지우고자 하는 원소가 없음
        raise Exception("No Such Key")
    e = element(w)
    z = leftChild(w)
    if !isExternal(z): # 왼쪽 자식이 external이 아님
        z = rightChild(w)
    if isExternal(z): # 자식 중에 외부 노드가 있으면
        reduceExternal(z) # 그냥 지우면 되는데
    else:
        y = inOrderSucc(w) # 중위 후계자 찾기
        z = leftChild(y)
        w.elem = y.elem
        w.key = y.key
        reduceExternal(z)
    return e

이진 탐색 트리의 성능

높이 $h$의 이진 탐색 트리로 구현된 원소 $n$개의 이진 탐색 트리는 $O(n)$ 공간을 사용하며, 탐색, 삽입 삭제를 모두 $O(h)$ 시간에 수행한다.

이때, $h$는 최선의 경우 $O(\log n)$이고 최악의 경우 $O(n)$이다.