12. Binary Search Trees

탐색 트리 자료 구조는 SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE 연산을 지원한다. 이 연산은 트리의 높이에 비례하며, 노드 n개의 완전 이진 트리라면 \Theta(\lg n)의 최악 수행 시간을 갖는다. 트리가 한 쪽으로 쏠린 경우라면 \Theta(n)이 되지만, 무작위적으로 생성된 이진 탐색 트리의 높이는 O(\lg n)이므로, 평균적 최악 수행 시간은 \Theta(\lg n)이다. 실제로는 무작위적으로 생성됨을 보장할 수 없기 때문에 스스로 균형을 맞추는 이진 트리 등을 쓴다.

12.1. What is a binary search tree?

이진 트리는 데이터 key와, 각각 왼쪽 자식/오른쪽 자식/부모를 향한 포인터인 left, right, p를 멤버로 갖는 자료구조이다. 자식이나 부모가 없으면 해당 포인터는 NIL이 된다. 루트 노드는 트리 내 부모가 없는 유일한 노드이다. 다음 특성을 만족하면 이진 탐색 트리이다.

x가 노드일 때, y가 x의 왼쪽 부분 트리 내의 노드이면 y.key \leq x.key, x의 오른쪽 부분 트리 내의 노드이면 y.key \geq x.key

이진 탐색 트리 특성은 트리 내의 키를 간단한 중위 순회 알고리즘으로 정렬된 순으로 출력시킨다. (전위 순회후위 순회 알고리즘도 있다.)

INORDER-TREE-WALK(x)
if x ≠ NIL
    INORDER-TREE-WALK(x.left)
    print x.key
    INORDER-TREE-WALK(x.right)

Theorem. 노드 n개의 부분 트리의 루트를 x라고 할 때, INORDER-TREE-WALK(x)는 \Theta(n) 시간을 소모한다.

12.2. Querying a binary search tree

이진 탐색 트리의 높이가 h일 때 SEARCH 외에도 MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR 연산을 O(h) 시간 내에 수행할 수 있다.

Searching

탐색은 다음과 같이 수행한다.

TREE-SEARCH(x, k)
if x == NIL or k == x.key
    return x
if k < x.key
    return TREE-SEARCH(x.left, k)
else
    return TREE-SEARCH(x.right, k)

다음과 같이 반복적 알고리즘으로 쓸 수도 있다.

ITERATIVE-TREE-SEARCH(x, k)
while x ≠ NIL and k ≠ x.key
    if k < x.key
        x = x.left
    else
        x = x.right
return x

Minimum and maximum

최소/최대값은 다음과 같이 찾는다.

TREE-MINIMUM(x)
while x.left ≠ NIL
    x = x.left
return x
TREE-MAXIMUM(x)
while x.right ≠ NIL
    x = x.right
return x

Successor and predecessor

이진 탐색 트리에서는 어떤 노드의 바로 앞 순서나 바로 뒷 순서에 오는 키를 가진 노드를 키 비교 없이 O(h) 시간에 찾을 수 있다.

TREE-SUCCESSOR(x)
if x.right ≠ NIL
    return TREE-MINIMUM(x.right)
y = x.p
while y ≠ NIL and x == y.right
    x = y
    y = y.p
return y

TREE-PREDECESSOR는 위의 코드와 정확히 대칭이다.

Theorem. 높이 h의 이진 탐색 트리에서 SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR를 O(h) 시간 내에 찾을 수 있다.

12.3. Insertion and deletion

삽입과 삭제를 하면서도 이진 탐색 트리 특성을 보존시키고 싶다.

Insertion

삽입은 다음과 같이 자취 포인터 y로 삽입될 장소의 부모 노드를 찾은 뒤 최종적으로 y와 z의 키를 비교해 삽입한다. O(h) 시간이 걸린다.

TREE-INSERT(T, z)
y = NIL
x = T.root
while x ≠ NIL
    y = x
    if z.key < x.key
        x = x.left
    else
        x = x.right
z.p = y
if y == NIL
    T.root = z // tree T was empty
else if z.key < y.key
    y.left = z
else
    y.right = z

Deletion

4가지 경우로 나눈다.

  • z가 왼쪽 자식이 없으면, z를 오른쪽 자식으로 대체한다.
  • z가 왼쪽 자식만 있으면, z를 왼쪽 자식으로 대체한다.
  • z가 왼쪽 자식과 오른쪽 자식이 모두 있으면, z의 바로 앞 순서에 오는 원소 y를 찾는다. y가 z의 오른쪽 자식이라면, z를 y로 대체한다.
  • z가 왼쪽 자식과 오른쪽 자식이 모두 있으면, z의 바로 앞 순서에 오는 원소 y를 찾는다. y가 z의 오른쪽 자식이 아니라면, y는 z의 오른쪽 부분 트리에 있다. 이 경우에는 y를 오른쪽 자식으로 대체한 뒤, z를 y로 대체한다.

이를 위해 다음의 서브루틴 TRANSPLANT를 정의한다. 이는 부분 트리 u를 부분 트리 v로 대체하는 루틴이다.

TRANSPLANT(T, u, v)
if u.p == NIL
    T.root = v
else if u == u.p.left
    u.p.left = v
else
    u.p.right = v
if v ≠ NIL
    v.p = u.p

이후 삭제는 다음과 같이 정의된다. 이는 O(h) 시간이 걸린다.

TREE-DELETE(T, z)
if z.left == NIL
    TRANSPLANT(T, z, z.right)
else if z.right == NIL
    TRANSPLANT(T, z, z.left)
else
    y = TREE-MINIMUM(z.right)
    if y.p ≠ z
        TRANSPLANT(T, y, y.right)
        y.right = z.right
        y.right.p = y
    TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y

Theorem. 높이 h의 이진 탐색 트리에서 INSERT와 DELETE는 O(h) 시간에 수행된다.

12.4. Randomly built binary search trees

이진 탐색 트리의 높이는 원소가 삽입/삭제되는 패턴에 따라 달라질 수 있다. 예를 들어 작은 원소부터 쭉 삽입되면 높이 n – 1의 체인이 될 것이다. 안타깝게도 삽입/삭제가 섞일 경우의 평균 높이에 대해서는 거의 알려진 것이 없다. 반면에 트리가 삽입만으로 생성된다면 무작위 생성 이진 탐색 트리의 평균 높이를 구할 수 있다. 이 때 입력 키 n개의 n!개의 삽입 순서가 나올 확률은 같다고 하자. (이것은 이진 탐색 트리들이 구성될 확률이 같은 것과는 다르다.)

Theorem. n개의 서로 다른 키들로 생성되는 무작위 생성 이진 탐색 트리의 평균 높이는 O(\lg n)이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중