12 Binary Search Tree

12 Binary Search Trees

그 search tree 자료구조는 SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, 그리고 DELETE를 포함하여 많은 dynamic-set operations을 지원한다. 따라서, 우리는 dictionary와 우선순위 큐 둘 다로서 search tree를 사용할 수 있다.

binary search tree에 대한 기본 연산들은 트리의 높이에 비례한 시간이 걸린다. n개의 노드를 가진 a complete binary tree에 대해, 그러한 연산들은 $\Theta(lg\;n)$의 worst-case time에 작동한다. 만약 그 tree가 n개의 linear nodes의 chain을 갖는다면, 그러나, 그 같은 연산들은 $\Theta(n)$의 worst-case time이 걸린다. 우리는 SEction 12.4에서 그 randomly built binary search tree의 예상되는 height가 $O(lg\;n)$이라는 것을 볼 것이다. 이것은 그러한 트리에서 basic dynamic-set의 operations이 평균적으로 $\Theta(lg\;n)$의 시간이 걸리게 하기 위해서이다.

실제로, 우리는 항상 binary search trees가 무작위로 구성되게 보장할 수 없지만, 그러나 우리는 기본 연산들에 대해 좋게 보장된 worst-case performance로 binary search trees의 변형을 설계할 수 있다. Chapter 13은 높이 $O(lg\;n)$을 가진 그러한 변형인 red-black trees를 보여준다. Chapter 18은 secondary (disk) storage에서 databases를 유지하기에 특히 좋은 B-trees를 소개한다.

binary search trees의 기본 특징들을 보여준 후에, 다음의 섹션들은 정렬된 순서로 어떻게 그것의 값을 출력하기 위해 binary search tree 를 어떻게 순회하는지, binary search tree에서 한 값을 찾는 방법, minimum or maximum element를 찾는 방법, 한 element의 predecessor와 successor를 찾는 방법, 그리고 binary search tree에 삽입하거나 그거로부터 삭제하는 방법을 보여준다. trees의 기본 수학적 특성들은 Appendix B에서 나타난다.

 

12.1 What is a binary search tree?

이름이 암시하듯이, a binary search tree는 그림 12.1에서 보여지듯이 binary tree로 구성된다. 우리는 각 노드가 object인 linked data structure로 그러한 트리를 표현할 수 있다. key와 satellite data외에도, 각 노드는 left, right, 그리고 p의 attributes를 가지는데, 이것은 각각 그것의 왼쪽 자식, 오른쪽 자식, 부모에 대응되는 노드들을 가리킨다. 만약 한 child또는 parent가 없다면, 그 적절한 attribute는 value NIL를 포함한다. 그 root node는 parent가 NIL인 tree에서 유일한 node이다.

binary search tree에서 그 keys는 항상 binary-search-tree property를 만족하는 방식으로 저장된다:

x가 binary search tree에서 한 노드가 되도록 하자. 만약 y가 x의 left subtree에 있따면, 그러면 $y.key \leq x.key$이다. 만약 y가 x의 right subtree에 있다면, 그러면 $y.key \geq x.key$.

따라서, 그림 12.1(a)에서, 그 root의 key는 6이고, keys 2, 5 그리고 그것의 left subtree에 있는 5는 더 이상 6보다 더 크지 않고, right subtree에 있는 7과 8은 6보다 더 작지 않다. 같은 특성이 트리에 있는 모든 노드에 대해 유효하다. 예를들어, root의 left child에 있는 key 5는 그 노드의 left subtree에 있는 key 2보다 작지 않고, right subtree에 있는 key 5보다 더 크지 않다.

그 binary-search-tree property는 inorder tree walk라고 불려지는 간단한 재귀 알고리즘으로 정렬된 순서로 binary search tree에 있는 모든 keys를 출력하게 해준다. 이 알고리즘은 left subtree의 값을 출력하는 것과 right subtree에 있는 값들을 출력하는 사이에, 한 subtree의 root의 key를 출력하기 때문에 그렇게 이름지어 졌다. (유사하게, preorder tree walk는 둘 중 하나의 subtree에 있는 값들 전에 root를 출력하고, postorder tree walk는 그것의 subtrees에 있는 값들 후에 root를 출력한다.) binary search tree T에 있는 모든 elements를 출력하는 다음의 procedure를 사용하기 위해, 우리는 INORDER-TREE-WALK(T.root)를 호출한다.

INORDER-TREE-WALK(x)
1   if x != NIL
2       INORDER-TREE-WALK(x.left)
3       print x.key
4       INORDER-TREE-WALK(x.right)

예시로, inorder tree walk는 그림 12.1에서 두 개의 binary search trees각각에서 2, 5, 5, 6, 7, 8의 순서로 키들을 출력한다. 그 알고리즘의 정확성은 binary-search-tree property로부터 직접 유추된다.

한 n-node binary search tree를 순회하는 것은 $\Theta(n)$의 시간이 걸린다. 왜냐하면 초기 호출 이후에, 그 procedure은 그 자체로 재귀로 정확히 그 트리에 각 노드에 두 번씩 요구한다 - 그것의 left child에 한 번, 그리고 오른족 child에 한 번. 다음의 정리는 inorder tree walk를 수행하는데 linear time이 걸린다는 formal proof를 주는 정리이다.

Theorem 12.1

만약 x가 n-node subtree의 root라면, 그러면 INORDER-TREE-WALK(x)의 호출은 $\Theta(n)$ time이 걸린다.

Proof $T(n)$을 n-node subtree의 root에 대해 INORDER-TREE-WALK에 의해 호출될 때 그것에 의해 걸리는 시간으로 표기하자. INORDER-TREE-WALK는 그 subtree의 모든 n nodes를 방문하기 때문에, 우리는 $T(n) = \Omega(n)$를 가지게 된다. $T(n) = O(n)$라는 것을 보여주는 것이 남는다.

INORDER-TREE-WALK는 한 empty subtree (테스트를 위해 $x \neq NIL$)에 작고 상수 양의 시간이 걸리기 때문에, 우리는 어떤 상수 $c > 0$에 대해 $T(0) = c$를 가진다.

$n > 0$에 대해, INORDER-TREE-WALK가 한 노드 x에 대해 호출된다고 가정하자. 그 x의 left subtree는 k nodes를 가지고 있고, right subtree는 n - k - 1 nodes를 가지고 있다. INORDER-TREE-WALK(x)를 수행하는 시간은 어떤 상수 $d > 0$에 대해 $T(n) \leq T(k) + T(n-k-1) + d$로 제한된다. 그 d는 INORDER-TREE-WALK(x)를 body를 실행하는데 걸리는 시간의 상한을 반영한다. 그리고 recursive calls에 쓰이는 시간을 제외한다.

우리는 $T(n) = O(n)$라는 것을 보여주기 위해 치환 방법을 사용한다. $T(n) \leq (c+d)n + c$라는 것을 보여주어서. $n = 0$에 대해, 우리는 $(c+d) \cdot 0 + c = c = T(0)$를 갖는다. $n >0$에 대해, 우리는 다음을 갖는다

$$\begin{split} T(n) & \leq T(k) + T(n-k-1) + d\\ & = ((c+d)k + c) + ((c+d)(n-k-1) + c) + d \\ & = (c+d)n + c - (c+d) + c+d & = (c+d)n +c, \end{split}$$

그리고 이것이 증명을 마무리한다.

12.2 Querying a binary search tree

우리는 binary search tree에서 저장된 key를 탐색할 필요가 있다. SEARCH operation외에, binary search trees는 MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR같은 queries를 지원할 수 있다. 이 섹션에서, 우리는 이러한 연산들에 대해 조사할 것이고, height가 h인 어떤 binary search tree에서 $O(h)$ 시간에 각각을 어떻게 지원하는지를 보여줄 것이다.

Searching

우리는 binary search tree에서 주어진 key를 가진 노드를 찾기 위해 다음의 procedure를 사용한다. tree의 root에 대한 포인터가 주어지고, key k가 주어진다면, TREE-SEARCH는 key k를 가진 노드에 대한 포인터가 존재한다면 그것을 반환한다; 그렇지 않다면 그것은 NIL를 반환한다.

xxxxxxxxxx
TREE-SEARCH(x,k)
1   if x == NIL or k == x.key
2       return x
3   if k < x.key
4       return TREE-SEARCH(x.left, k)
5   else return TREE-SEARCH(x.right, k)

그 procedure는 root에서 그것의 탐색을 시작하고, tree에서 아래쪽으로 간단한 경로를 따라간다. 그림 12.2에서 보여지듯이. 그것이 만나는 각 노드 x에 대해, 그것은 key k와 x.key를 비교한다. 만약 그 두 키가 같다면, 그 탐색은 종료된다. 만약 k가 x.key보다 더 작다면, 그 탐색은 x의 왼쪽 subtree에서 계속된다. 왜냐하면 binary-search tree property는 k가 right subtree에서 저장될 수 없다는 것을 암시하기 떄문이다. 대칭적으로 만약 k가 x.key보다 더 크다면, 그 탐색은 right subtree에서 계속된다. 재귀 동안 만난 그 노드들은 그 tree의 root에서 아래로 가는 simple path를 만들고, 따라서 TREE-SEARCH의 running time은 $O(h)$이고, 여기에서 h는 tree의 높이이다.

우리는 그 재귀를 while loop로 "unrolling"하여 iterative 방식으로 재작성할 수 있다. 대부분의 컴퓨터에서, iterative version이 좀 더 효율적이다.

xxxxxxxxxx
ITERATIVE-TREE-SEARCH(x,k)
1   while x != NIL and k != x.key
2       if k < x.key
3           x = x.left
4       else x = x.right
5   return x

 

Minimum and maximum

우리는 binary search tree에서 그것의 key가 가장 작은 것을, NIL를 만날 때 까지 root에서 left child pointers를 따라가서, 찾을 수 있다, 그림 12.2에서 보여지듯이. 다음의 procedure는 한 주어진 노드 x를 root로 하는 subtree에서 minimum element에 대한 포인터를 반환한다. 우리는 그것이 non-NIL를 가정한다.

xxxxxxxxxx
TREE-MINIMUM(x)
1   while x.left != NIL
2       x = x.left
3   return x

그 binary-search-tree property는 TREE-MINIMUM이 옳다는 것을 보장한다. 만약 한 노드 X가 어떠한 left subtree가 없다고 한다면, 그러면 x의 right subtree에 있는 모든 key가 적어도 x.key만큼 크기 떄문에, x를 root로 하는 subtree에 있는 minimum key는 x.key이다. 만약 node x가 left subtree를 가진다면, right subtree에 있는 어떠한 key는 x.key보다 더 작지 않기 때문에, left subtree에 있는 모든 key는 x.key보다 더 크지 않다. x를 루트로 하는 subtree에서 최소 key는 x.left를 root로 하는 subtree에 있다.

TREE-MAXIMUM에 대한 의사코드는 대칭적이다:

xxxxxxxxxx
TREE-MAXIMUM(x)
1   while x.right != NIL
2       x = x.right
3   return x

 

Successor and predecessor

binary search tree에서 한 노드가 주어진다면, 가끔씩 우리는 inorder tree walk에 의해 결정되는 sorted order에서 그것의 successor를 찾을 필요가 있다. 만약 모든 key가 다르다면, 한 노드 x의 successor는 $x.key$보다 더 큰 가장 작은 key를 가진 노드이다. binary search tree의 구조는 우리가 키를 비교하지 않고 한 노드의 successor를 결정하게 해준다. 다음의 procedure는 한 노드 x의 successor가 존재한다면 그것을 반환한다. 만약 x가 tree에서 가장 큰 key라면 NIL를 반환한다.

xxxxxxxxxx
TREE-SUCCESSOR(x)
1   if  x.right != NIL
2       return TREE-MINIMUM(x.right)
3   y = x.p
4   while y != NIL and x == y.right
5       x = y
6       y = y.p
7   return y

우리는 두 가지 경우에서 TREE-SUCCESSOR의 코드를 분해한다. 만약 노드 x의 그 right subtree가 비어있지 않다면, x의 successor는 x의 right subtree에 있는 가장 왼쪽에 있는 노드이고, 우리는 TREE-MINIMUM(x.right)를 호출하여 line 2에서 그것을 찾는다. 예를들어, 그림 12.2에서 key 15를 가진 노드의 successor는 key 17를 가진 노드이다.

반면에, Exercise 12.2-6이 너에게 보여달라고 요청했듯이, node x의 right subtree가 비어있다면, x는 successor y를 가지고, 그러고나서, y는 x의 lowest ancestor가 되는데, 그 y의 left child는 또한 x의 ancestor이다. 그림 12.2에서 key 13의 node의 successor는 key 15를 가진 노드이다. y를 찾기 위해, 우리는 그것의 부모가 left child인 노드를 만날 때 까지 x로 부터 트리의 위로 올라간다; TREE-SUCCESSOR의 lines 3-7은 이 케이스를 다룬다.

height h의 tree에 대해 TREE-SUCCESSOR의 작동시간은 $O(h)$이다. 왜냐하면 우리는 tree를 simple path up하는 것을 따라거나, simple path down하는 것을 따르기 때문이다. TREE-SUCCESSOR와 대칭인 TREE-PREDECESSOR는 또한 $O(h)$ 시간에 작동한다.

비록 keys가 다르지 않을지라도, 우리는 각각 TREE-SUCCESSOR(x)와 TREE-PREDECESSOR(x)에 만들어진 호출로 반환된 노드로서 어떤 node x의 successor와 predecessor를 정의한다.

요약해서, 우리는 다음의 정리를 증명했다.

Theorem 12.2

우리는 각각은 height h인 binary search tree에서 $O(h)$ time에 작동하도록 SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR인 dynamic-set operations을 구현할 수 있다.

 

12.2-1

 

12.2-2

 

12.2-3

TREE-PREDECESSOR procedure를 작성해라. Ans : predecessor는 한 노드 x보다 작은 것 중 가장 큰 것이다. 따라서 다음과 같다.

xxxxxxxxxx
TREE-PREDECESSOR(T, x)
1   if x.left != NIL
2       return TREE-MAXIMUM(T, x.left)
3   y = x.p
4   while y != NIL and x == y.left
5       x = y
6       y = y.p
7   return y

...

 

12.3 Insertion and deletion

insertion과 deletaion의 연산은 binary search tree에 의해 나타내어지는 dynamic set이 변하도록 한다. 그 자료구조는 이 변화를 반영하기 위해 수정되어야 하지만, binary-search-tree property가 계속해서 유효한 방식으로 해야 한다. 우리가 보게 되듯이, 새로운 element를 넣기 위해 tree를 수정하는 것은 상대적으로 간단하지만, deletion을 다루는 것은 어느정도 복잡하다.

Insertion

새로우 value $v$를 binary search tree $T$에 넣기위해, 우리는 TREE-INSERT procedure를 사용한다. 그 procedure는 한 노드 $z$를 취하는데, $z.key = v, z.left = NIL, \text{ and } z.right = NIL$이다. 그것은 $z$를 tree에 적절한 위치에 넣어서 T와 $z$의 어떤 attributes를 수정한다.

xxxxxxxxxx
TREE-INSERT(T,z)
1   y = NIL
2   x = T.root
3   while x != NIL
4       y = x
5       if z.key < x.key
6           x = x.left
7       else x = x.right
8   z.p = y
9   if y == NIL
10      T.root = z      // tree T was empty
11  else if z.key < y.key
12      y.left = z
13  else y.right = z

그림 12.3은 TREE-INSERT가 작동하는 방법을 보여준다. procedure TREE-SEARCH and ITERATICE-TREE-SEARCH 처럼, TREE-INSERT는 tree의 root에서 시작하고, 그 pointer x는 그 input item $z$와 바꿀 NIL를 찾아서 simple path를 따라 아래로 내려간다. 그 procedure는 x의 parent인 trailing pointer를 유지한다. 초기화 후에, lines 3-7에 있는 while loop는 이러한 두 개의 포인터들이 tree의 아래로 내려가게 하고, $x$가 $NIL$이 될 때 까지, $z.key$와 $x.key$에 대한 비교에 따라 왼쪽 오른쪽으로 간다. 이 $NIL$은 우리가 input item $z$를 위치시키고 싶은 위치를 차지한다. 우리는 trailing pointer $y$가 필요한데, 왜냐하면 우리가 $z$가 속한 $NIL$를 발견할 즈음에, 그 탐색은 바뀔 필요가 있는 노드를 너머서 한 단계 더 진행했기 때문이다. Lines 8-13은 $z$가 삽입되도록 하는 포인터를 설정한다.

search trees에서 다른 primitive operations같이, 그 procedure TREE-INSERT는 height h인 tree에서 $O(h)$ time에 작동한다.

 

Deletion

binary search tree $T$로부터 한 node $z$를 삭제하기 위한 전반적인 전략은 세 가지 기본 케이스들을 갖지만, 우리가 보게 되듯이, 그 케이스들 중 하나가 조금 까다롭다.

• 만약 $z$가 자식이 없다면, 그러면 우리는 그것의 부모가 $z$를 그것의 자식으로서 $NIL$로 교체하게 수정하여 간단히 그것을 제거한다.
• 만약 $z$가 한 자식을 가진다면, 우리는 그 child가 tree에서 $z$의 위치를 가지도록 승격시키는데, $z$의 부모가 $z$를 $z$의 자식으로 교체하도록 하여 수정한다.
• 만약 $z$가 두 자식을 갖는다면, 그러면 우리는 z의 successor y를 찾는다 - 그리고 그 successor y는 $z$의 right subtree에 있다 - 그리고 y가 tree에서 $z$의 위치를 갖게 한다. 그 $z$의 원래 right subtree의 나머지는 y의 새로운 right subtree가 되고, z의 left subtree는 y의 새로운 left subtree가 된다. 이 경우는 까다롭다. 왜냐하면 우리가 보게 되듯이, y가 z의 right child라는 것이 중요하기 때문이다.

binary search tree T에서 한 주어진 노드 z를 지우기 위한 procedure는 T와 z에 대한 포인터들을 인자로 받는다. 그것은 그림 12.4에서 보여지는 4개의 경우를 고려하여 이전에 열거된 3개의 경우와는 조금 다르게 그것의 케이스들을 구성한다.

• 만약 z가 어떠한 left child를 가지고 있지 않다면 (그림의 part(a)), 그러면 우리는 z를 그것의 right child로 바꾼다. 그 right child는 NIL일 수도, 아닐 수도 있다. z의 right child가 NIL일 떄, 이 경우는 z가 어떠한 자식도 없는 상황을 처리한다. z의 right child가 non-NIL일 때, 이 케이스는 z가 right child인 한 자식을 가지는 상황을 처리한다.

• 만약 z가 left child인 한 자식을 갖는다면 (그림의 part(b)), 그러면 우리는 z를 그것의 left child로 대체한다.

• 만약 그렇지 않다면, z는 left와 right child 둘 다 갖는다. 우리는 z의 successor y를 찾는데, 그 successor y는 z의 right subtree에 놓여있고, 어떠한 left child를 가지지 않는다 (see Exercise 12.2-5). 우리는 그것의 현재 위치에서 y를 붙이고 싶고, 그것이 tree에서 z를 교체하도록 하고 싶다.

  • 만약 y가 z의 right child (part(c))라면, 그러면 우리는 z를 y로 교체한다. y의 right child를 가만히 두고.
  • 만약 그렇지 않다면, y는 z의 right subtree에 놓여있지만, 그것은 z의 right child가 아니다 (part (d)). 이 경우에, 우리는 y를 그것 자신의 right child로 교체하고, 그러고나서 z를 y로 교체한다.

binary search tree내에서 subtrees를 움직이기 위해서, 우리는 subroutine TRANSPLAN를 정의한다. 이것은 그것의 부모의 자식인 한 subtree를 또 다른 subtree로 교체한다. TRANSPLANT가 한 노드 $u$를 root로 하는 subtree를 노드 $v$를 root로 하는 subtree로 교체할 떄, node $u$의 부모는 노드 $v$의 부모가 되고, $u$의 부모는 $v$를 그것의 적절한 자식으로서 가지게 된다.

xxxxxxxxxx
TRANSPLANT(T,u,v)
1   if u.p == NIL
2       T.root = v
3   elseif u == u.p.left
4       u.p.left = v
5   else u.p.right = v
6   if v != NIL
7       v.p = u.p

Lines 1-2는 $u$가 T의 root인 경우를 처리한다. 만약 그렇지 않다면, $u$는 그것의 부모의 left or right child이다. Lines 3-4는 만약 u가 left child라면, u.p.left를 업데이트하고, right child라면 line 5는 u.p.right를 업데이트 한다. 우리는 v가 NIL이 되는 것을 허용하고, lines 6-7은 v가 NIL이 아니라면 v.p를 업데이트 한다. TRANSPLANT가 v.left와 v.right를 업데이트하려고 하지 않는다는 것을 주목해라; 그렇게 하거나 그렇게 하지 않는 것은 TRANSPLAN T의 호출자의 책임이다.

TRANSPLANT procedure가 준비되고, binary search tree T로부터 node z를 삭제하는 procedure가 여기 있다:

xxxxxxxxxx
TREE-DELETE(T,z)
1   if z.left == NIL
2       TRANSPLANT(T, z, z.right)
3   elseif z.right == NIL
4       TRANSPLANT(T, z, z.left)
5   else y = TREE-MINIMUM(z.right)
6       if y.p != z
7           TRANSPLANT(T, y, y.right)
8           y.right = z.right
9           y.right.p = y
10      TRANSPLANT(T,z,y)
11      y.left = z.left
12      y.left.p = y

그 TREE-DELETE procedure는 다음과 같이 4개의 cases를 실행한다. Lines 1-2는 node z가 어떠한 left child를 가지지 않는 경우를 처리하고, lines 3-4는 z가 left child를 가지지만, right child를 가지지 않는 경우를 처리한다. Line 5-12는 나머지 두 경우를 처리하는데, z가 두 자식을 갖는 경우이다. Line 5는 z의 successor인 y를 찾는다. z는 비어있지 않는 right subtree를 가지기 때문에, 그것의 successor는 가장 작은 키를 가진 subtree의 노드임에 틀림없다; 그러므로 TREE-MINIMUM(z.right)에 대한 호출을 한다. 우리가 이전에 기재했듯이, y는 어떠한 left child를 가지지 않는다. 우리는 그것의 현재 위치에서 y를 잇고 싶고, 그것이 tree에서 z를 대체해야 한다. 만약 y가 z의 right child라면, 그러면 lines 10-12는 z의 부모의 한 자식을 y로 교체하고, y의 left child를 z의 left child로 교체한다. 만약 y가 z의 left child가 아니라면 (@Chan : 여기는 y가 z의 바로 아래의 right child가 아니라면 이라고 해야하지 않나 싶다), lines 7-9는 y를 y의 부모의 자식으로서 y의 right child로 교체하고, z의 right child를 y의 right child로 바꾼다. 그러고나서 lines 10-12는 z를 z의 부모의 자식으로서 y로 바꾸고, y의 left child를 z의 left child로 교체한다.

TRANSPLANT에 대한 호출을 포함하는 TREE-DELETE의 각 line은 상수 시간이 걸리는데, line 5에서의 TREE-MINIMUM에 대한 호출을 제외하고 이다. 따라서, TREE-DELETE는 height h의 tree에서 $O(h)$ time에 작동한다.

요약해서, 우리는 다음의 정리를 증명했다.

 

Theorem 12.3

height h인 binary search tree에서 $O(h)$ time에 각 연산이 작동하도록, 우리는 dynamic-set operations INSERT와 DELETE를 구현할 수 있다.

 

12.4 Randomly built binary search trees

우리는 binary search tree에 대한 기본 연산 각각이 $O(h)$ time에 작동하는 것을 보여주었다. 여기에서 $h$는 tree의 높이이다. 그러나, binary search의 높이는 다양한데, 왜냐하면 items들이 삽입되고 삭제되기 때문이다. 예를들어, 만약 n개의 items들이 확실히 증가하는 순서로 삽입된다면, 그 트리는 $n -1$의 높이의 chain이 될 것이다. 반면에 , Exercise B.5-4는 $h \geq \lfloor lg\; n \rfloor$라는 것을 보여주었다. quicksort와 관련하여, 우리는 평균 케이스의 행동이 worst case보다 best case에 더 가깝다는 것을 보여줄 수 있다.

불행하게도, insertion과 deletion이 이진 탐색 트리를 만들기 위해 둘 다 사용될 때, binary search tree의 평균 높이에 대해 알려진 것은 없다. 그 트리가 insertion으로만 생성될 때, 그 분석은 다루기 쉽다. 그러므로, n개의 keys에 대해 randomly built binary search tree를 초기 empty tree에 random 순서로 keys들을 넣어서 발생하는 것으로 정의하자. (Exercise 12.4-3는 이 개념이 n개의 keys에 대한 모든 binary search tree와 동일하게 같다는 가정과 다르다는 것을 보여줄 것을 요청한다.) 이 섹션에서, 우리는 다음의 정리를 증명할 것이다.

 

Theorem 12.4

n개의 별개의 keys에 대해 randomly built binary search tree의 예상되는 높이는 $O(lg \; n)$이다.

Proof 우리는 한 randomly built binary search tree의 높이를 측정하는데 도와주는 세 개의 랜덤 변수를 정의하여 시작한다. 우리는 n개의 keys에 대한 randomly built binary search tree의 높이를 $X_n$으로 표기한다. 우리는 exponential height를 $Y_n = 2^{X_n}$으로 정의한다. 우리가 n개의 keys에 대해 binary search tree를 구성할 때, 우리는 한 key를 그 root의 key로서 선택하고, $R_n$이 n개의 keys들의 집합내에서 이 key의 rank를 가지는 random 변수를 표기하도록 하자; 즉, $R_n$은 만약 그 key의 집합이 정렬되었다면 이 key가 차지할 position을 가지고 있다. $R_n$의 값은 동일하게, 집합 $\{1, 2, \dots, n\}$의 어떤 원소일 것이다. 만약 $R_n = i$라면, 그러면 그 root의 left subtree는 $i - 1$개의 keys에 대한 randomly built binary search tree이다. 그리고 right subtree는 $n - i$개의 keys에 대한 randomly built binary search tree이다. 한 binary tree의 height가 root의 두 개의 subtrees의 높이보다 한 개 더 크기 때문에, 한 binary tree의 exponential height는 그 root의 두 개의 subtrees의 exponential heights보다 두 배 더 크다. 만약 우리가 $R_n = i$라는 것을 안다면, 그것은 다음을 따른다

$$Y_n = 2 \cdot max(Y_{i-1}, Y_{n-i}).$$

base cases로서, 우리는 $Y_1 = 1$이라는 것을 가지는데, 왜냐하면 1개 노드를 가진 한 트리의 exponential height는 $2^0 = 1$이기 때문이다. 편리함을 위해, 우리는 $Y_0 = 0$으로 정의한다.

다음으로, indicator random variables $Z_{n,1}, Z_{n,2}, \dots, Z_{n,n}$을 정의하는데

$$Z_{n,i} = I \{\; R_n = i \; \}.$$

$R_n$은 $\{1, 2, \dots, n\}$의 어떤 원소일 것이기 때문에, 그것은 $i = 1, 2, \dots, n,$에 대해, $Pr\{R_n = i\} = 1/n$를 따른다. 그러므로, Lemma 5.1에 의해, 우리는 $i = 1, 2, \dots, n$에 대해 다음을 갖는다

$$\begin{align} E[Z_{n, i}] = 1/n &&&&& (12.1) \end{align}$$

왜냐하면 $Z_{n,i}$의 정확히 한 개의 값이 1이고 모든 다른 것은 0이기 때문에, 우리는 다음을 갖는다

$$Y_n = \sum^n_{i=1} Z_{n,i} (2 \cdot max(Y_{i-1}, Y_{n-i})).$$

우리는 $E[Y_n]$이 $n$에서 다항식이라는 것을 보여줄 것이다. 그것은 궁극적으로 $E[X_n] = O(lg \;n)$이라는 것을 암시할 것이다.

우리는 indicator random variable $Z_{n,i} = I \{R_n = i\}$가 $Y_{i-1}$과 $Y_{n-i}$의 값과 독립적이라고 주장한다. $R_n = i$를 선택하여, 왼쪽 subtree (exponential height가 $Y_{i-1}$)가 $i -1$개의 keys에 대해 random으로 built되었는데, 그것의 ranks는 $i$보다 더 작다. 이 subtree는 $i - 1$개의 keys에 대해 어떤 다른 randomly built binary search tree와 같다. 그것이 포함하는 키의 개수 외에도, 이 subtree의 structure는 $R_n = i$의 선택에 전혀 영향을 받지 않고, 그러므로 그 random 변수 $Y_{i-1}$과 $Z_{n,i}$는 독립적이다. 마찬가지로, exponential height 가 $Y_{n-i}$인 right subtree는 $n - i$ keys에 대해 randomly built되었고, 그 키들의 ranks는 $i$보다 더 크다. 그것의 구조는 $R_n$의 값과 독립적이고, 그래서 그 확률 변수 $Y_{n-i}$와 $Z_{n,i}$는 독립적이다. 그러므로 우리는 다음을 갖는다

$$\begin{align} E[Y_n] & = E \Bigg[ \sum^n_{i=1}Z_{n,i} (2 \cdot max(Y_{i-1}, Y_{n-i})) \Bigg] \\ & = \sum^n_{i = 1} E [Z_{n,i} (2 \cdot max(Y_{i-1}, Y_{n-i}))] \;\; \text{(by linearity of expectation)} \\ & = \sum^n_{i=1} E[Z_{n,i}] E[2 \cdot max(Y_{i-1}, Y_{n-i})] \;\; \text{(by independence)} \\ & = \sum^n_{i=1} \frac{1}{n} \cdot E[2 \cdot max(Y_{i-1}, Y_{n-1})] \;\; \text{(by equation (12.1))} \\ & = \frac{2}{n} \sum^n_{i=1}E[max(Y_{i-1}, Y_{n-i})] \;\; \text{(by equation (C.22))} \\ & \leq \frac{2}{n} \sum^n_{i=1} (E[Y_{i-1}] + E_[Y_{n-i}]) \;\; \text{(by Exercise C.3-4)} \end{align}$$

각 항 $E[Y_0], E_[Y_1], \dots, E[Y_{n-1}]$은 마지막 합에서 두 번 나타나기 때문에, $E[Y_{i-1}]$로서 한 번, 그리고 $E[Y_{n-i}]$로 한 번, 우리는 다음의 반복을 갖는다

$$\begin{split} E[Y_n] \leq \frac{4}{n} \sum^{n-1}_{i=0} E[Y_i] \;\;\;\;\;\;\; (12.2) \end{split}$$

치환를 사용하여, 우리는 모든 양의 정수 $n$에 대해, (12.2)의 반복은 다음의 해를 갖는다

$$E[Y_n] \leq \frac{1}{4} \begin{pmatrix} n +3 \\ 3 \end{pmatrix}.$$

그렇게 할 떄, 우리는 다음의 항등식을 사용할 것이다

$$\sum^{n-1}_{i=0} \begin{pmatrix} i+3 \\ 3 \end{pmatrix} = \begin{pmatrix} n + 3 \\ 4 \end{pmatrix}$$

(Exercise 12.4-1은 너에게 이 항등식을 증명하라고 요청한다.)

base caese에 대해, 우리는 bounds $0 = Y_0 = E[Y_0] \leq (1/4) \begin{pmatrix}3 \\ 3 \end{pmatrix} = 1/4$이고, $1 = Y_1 = E[Y_1] \leq (1/4) \begin{pmatrix} 1 + 3 \\ 3 \end{pmatrix}$를 가진다는 것을 유의한다. inductive case의 경우에 대해, 우리는 다음을 갖는다.

$$\begin{split} E[Y_n] & \leq \frac{4}{n} \sum^{n-1}_{i=0} E[Y_i] \\ & \leq \frac{4}{n} \sum^{n-1}_{i=0} \frac{1}{4} \begin{pmatrix} i + 3 \\ 3 \end{pmatrix} \;\; \text{(by the inductive hypothesis)} \\ & = \frac{1}{n} \sum^{n-1}_{i=0} \begin{pmatrix} i + 3 \\ 3 \end{pmatrix} \\ & = \frac{1}{n} \begin{pmatrix} n + 3 \\ 4 \end{pmatrix} \;\; \text{(by equation (12.3))} \\ & = \;\; ... \\ & = \frac{1}{4} \begin{pmatrix} n + 3 \\ 3 \end{pmatrix} \end{split}$$

우리는 $E[Y_n]$를 제한했지만, 우리의 궁극적 목표는 $E[X_n]$를 제한하는 것이다. Exercise 12.4-4가 너에게 보이라고 요청하듯이, 그 함수 $f(x) = 2^x$는 convex이다 (1199 페이지를 보아라). 그러므로, 우리는 Jensen의 부등식 (C.26)을 이용할 수 있다. 그리고 그것은 말한다

$$\begin{split} 2^{E[X_n]} & \leq E[2^{X_n}] \\ = E[Y_n] \end{split}$$

그리고 다음으로

$$\begin{split} 2^{E[X_n]} & \leq \frac{1}{4} \begin{pmatrix} n + 3 \\ 3 \end{pmatrix} \\ & = \frac{1}{4} \cdot \frac{(n+3)(n+2)(n+1)}{6} \\ & = \frac{n^3 + 6n^2 + 11n + 6}{24} \end{split}$$

양쪽에 로그를 취하는 것은 $E[X_n] = O(lg \;n)$을 준다.