[Data Structures & Algorithms] Binary Search Tree

Binary Search Tree

• A binary tree
• Every node has a key (= value).
• Every node’s key K is
  • ① larger than all keys in its left subtree
  • ② smaller than all keys in its right subtree.

구현

BST : Linked List로 구현

• Node 구조

struct node *BST_ptr;
struct node
  BST_ptr left
  int data
  BST_ptr right
BST_ptr T = NULL;

BST : Operations

• Find(=Search) : BST에서 원하는(임의)값 X를 찾아라
• Insert : 새로운 값 X를 BST에 삽입
• Delete : 필요없는 값 X를 BST에서 삭제
• Find-Max : 가장 큰 값 X를 찾아라
• Find-Min : 가장 작은 값 X를 찾아라
• Find_Successor : X 다음으로 큰 값을 찾아라
• Sort : BST에 있는 모든 key값을 오름차순으로 정렬하여 출력

Find

• BST로부터 원하는 key 값 X를 갖는 node를 search;

BST_ptr SEARCH(BST_ptr T; int X)
/* 찾고자 하는 key X를 갖는 node를 찾아서 반환, 만약
없으면 NULL을 반환. T는 처음에 root를 가리킴 */
{
  if (T == NULL), return NULL; /* 비었거나, 실패 */
  if (X == T -> data) return T; /* 성공 */
  if (X < T -> data) return SEARCH(T -> left, X) /* T가 왼쪽으로 이동 */
  if (X > T -> data) return SEARCH(T -> right, X) /* T가 오른쪽으로 이동 */
}

Find : Smallest (Largest) Key

FIND_MIN (tree_ptr T)
{
  while (T -> left <> NULL)
    T = T -> left;
  return(T);
}

FIND_MAX (tree_ptr T)
{
  while (T -> right <> NULL)
    T = T -> right;
  return(T);
}

• Smallest key는 항상 맨 왼쪽 leaf 에, Largest key는 맨 오른 쪽 leaf에 항상 있음. 그리고 이 leaf들의 degree는 0 혹은 1을 가짐.

Insert

• Insert a new key X into BST
• 우선 SEARCH algorithm를 이용하여 X를 탐색;
• 만약 BST에 X가 있으면 이미 있으면 do nothing! 만약 없으면 X를 BST에 insert함.
• 여기서 X가 insert 되는 위치는?
  • : 항상 탐색이 종료된 leaf의 왼쪽 혹은 오른쪽 child (즉, null link)에서 발생;
• 이제 새로운 node를 할당 받은 후 여기에 X를 저장한 후 BST에 연결하면 삽입 완료.

Delete

• Delete a key X from BST; 우선 SEARCH algorithm를 이용하여 X를 탐색; If found, just delete it; Otherwise, return error.
• 다음 3 가지 경우가 발생; 즉, delete되는 node가
  • 1) Child가 없는 경우 : 그냥 삭제함.
  • 2) Child가 1 개인 경우 : 이 node의 parent의 해당 link를 이 node의 child를 가리키게 한 후, 삭제함.
  • 3) Child가 2 개인 경우 : 2 가지 방법, 삭제되는 node의 오른 쪽 (혹은 왼쪽) subtree 에서 가장 smallest (혹은 largest) key를 찾아, 이 key 값을 삭제되는 node에 대체함. 그리고 smallest (혹은 largest) key를 갖는 node를 삭제

Delete : Leaf node

• Leaf node의 삭제인 경우는 매우 간단함. 즉 삭제되는 leaf를 가리키는 Parent의 link 값 (위의 경우는 left child link)을 null로 하고, 삭제된 node를 storage pool로 반환함.

Delete : Node with degree 1

• 이 경우도 꽤 간단함. 즉 삭제되는 leaf를 가리키는 parent의 해당 link 값 (위의 경우 right child link)을 삭제되는 node의 child를 가리키도록 함. 삭제된 node는 storage pool로 반환함

Delete : Node with degree 2

• 삭제되는 node 10의 오른쪽 subtree에서 가장 작은 값(25)을 찾음.
• 10을 25로 대체한 후, 가장 작은 값을 갖는 node를 삭제함.
• 최종 결과

• 삭제되는 node 10의 왼쪽 subtree에서 가장 큰 값(5)을 찾음.
• 10을 5로 대체한 후, 가장 큰 값을 갖는 node를 삭제함.
• 최종 결과

성능 분석 : BST

• Find, Find_Max(Min), Insert, Delete are all bounded by O(h) where h is the height of the BST.
• 즉, root에서 부터 가장 아래에 있는 leaf 까지의 최대 길이 h.

• Height of BST depends on shapes of BST.
• Shapes of BST depends on order of insertions.

Shapes of BST

Average Case

• Average case는 각 node 당 평균 비교 회수로 산정됨
• 각 node 당 평균 비교회수 = 총 비교 회수 / 총 node 수(n)
• 총 비교 회수 = 각 node의 level들의 총 합 = Internal Path Length

• Average Internal path T(n) of BST with n nodes is known $O(n\log_2n)$.
• Thus, average case is T(n)/n is $O(\log_2n)$.
• In practice, if the keys are inserted in random order, all operations are $O(\log_2n)$. It is about $1.44\log_2n$

Worst Case

• However, Worst case is O(n) when BST is a form of skewed binary tree.
• 예 : 다음의 key들을 insert 할 때 worst case가 나오는 경우는?
  • {1, 2, 3, . . . 10}
  • Ascending order
  • Descending order
  • Zig-Zag order
  • etc.,
• Can we avoid O(n) in worst case? (즉, worst case에도 O(log2n)이 되도록 할 수 있는지?)
• 해결책 : “Balanced” BST

Performance Comparison

연습

• BST에 저장된 모든 key들을 오름 차순(increasing order)로 sort해서 출력하는 방법은?
• (혹은) 위의 key들을 내림 차순(decreasing order)로 출력하는 방법은?
• BST에서 임의의 key 값 X 바로 다음으로 큰 값 (= successor)을 갖는 key를 찾는 방법은?
• 다음의 key들로부터 생성될 수 있는 BST들을 모두 그리고, 각 BST에 대해 비교 회수를 계산하라. {for, if, while, else}