8. Binary Search Tree

 

 

Binary Search Tree

정의: binary tree in symmetric order

 

• Binary Tree: 노드로 구성되며, 각 노드는 최대 두 개의 자식(왼쪽과 오른쪽 자식)을 가진다.
• Symmetric Order
  • 모든 노드는 키를 갖는다.
  • 모든 노드의 키는
    • 왼쪽 하위 트리의 모든 키보다 큼
    • 오른쪽 하위 트리의 모든 키보다 작음
  • 중복된 노드가 없어야 한다.

 

이 트리에서

• 키 값이 가장 작은 노드
• 키 값이 가장 큰 노드
• 왼쪽 서브트리에서 가장 큰 키 값의 노드
• 오른쪽 서브트리에서 가장 작은 키 값의 노드

를 구하는 방법을 알아보자.

 

 

구조

• Node structure

1. Key:
2. Value:
3. Left:
4. Right:

 

• BST node structure

 

 

typedef int Key;
typedef char Value;
typedef char* pValue;

typedef struct node *pTree;
typedef struct node {
    pTree left; 	// left child
    pTree right; 	// right child
    Key key; 		// sorted by key
    pValue value;	// associated data with key
} node;

 

 

Operation

• Query
  • Search(T, k)

  bool search (pTree node, Key key) {
      if (node == NULL) return false;
      if (key == node->key) return true;
      if (key < node->key) search(node->left, key);
      search(node->right, key);
  }
  
  // iterative
  bool serachIterative (pTree node, Key key) {
      if (node == NULL) return false;
      while (node) {
          if (key == node->key) return true;
          if (key < node->key) node = node->left;
          else node = node->right;
      }
      return false;
  }
  

  
  
  • min/max: delete에서 다룸
  • successor : delete에서 다룸
  • predecessor: delete에서 다룸

 

• Travarsal

이진탐색트리를 순회할 때는 중위순회(in-order) 방식을 씁니다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회) 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있습니다.

순서: 11 20 23 31 39 50 75 77 80 98 99

 

• Insert(T, k)
  • 시간복잡도: $ O(h)$ , $h$는 트리의 depth
  • 알고리즘
    • Tree가 비어있으면 Root(T) = k
    • BST에서 null 노드를 만날 때까지 k를 검색하는 척하다가 삽입
    

  void insert(pTree node, Key key) {
      if (node == NULL) newNode(key);
      
      while (node != NULL) {
          if (node->key < key) node = node->right;
          else node = node->left;
      }
      
      node = newNode(key);    
  }
  

 

• Delete
  
  • case1: 자식노드가 없는 경우
  • => NULL로 대체
  
  • case2: 자식노드가 하나 있는 경우
    • left child인 경우
    • => 빈 자리에 left child가 들어감
    
    • right child인 경우
    • => 빈 자리에 right child가 들어감
  • case3: 자식노드가 두 개 있는 경우=> 삭제하려는 키 (5)의 predecessor인 4가 5의 자리를 대신한다.
    • predecessor: key[x]보다 작은 key 중에서 가장 큰 key를 가진 노드
      

      int predecessor (pTree ptr, Key key) {
          
      }
      
      int findMax(pTree ptr, Key key) {
          while ()
          
      }
      

    • findMax(node->left): 지우려는 노드를 root로 갖는 tree의 왼쪽 subtree에서 최댓값을 찾으면 될 것이다.
    • 1-3-4-5-6-7-9-10
    
    
    • successor: key[x]보다 큰 key 중에서 가장 작은 key를 가진 노드
      

      int successor (pTree ptr, Key key) {
          
      }
      
      int findMin(pTree ptr, Key key) {
          
      }
      

    • findMin(node->right): 지우려는 노드를 root로 갖는 tree의 오른쪽 subtree에서 최솟값을 찾으면 될 것이다.
    • 1-3-4-5-6-7-9-10
  

 

 

void Delete (pTree T, Key k) {
    
}

 

 

• Min/max
  • Balanced / Unbalanced tree
    • Balanced: 노드 수가 N일 때 최대 logN height를 갖는다.
    • Unbalanced: 노드 수가 N일 때 N에 가까운 height를 갖는다.
  
  
  Tree의 height 계산
  • height: root에서 leaf까지의 경로에 있는 최대 노드 수입니다.

  height(Tree) = 1 + max(Tree.left, Tree.right);
    
  // if (Tree.left < Tree.right) 
  //		Tree.right = 1 + max(Tree.right.left, Tree.right.right)
  
  // 이런식으로 쭉 내려가면서 null 노드 까지 recursively 내려가면 Tree 전체의 height를 구할 수 있다.
  

  시간복잡도: $ O(h)$ ,  $ h = \log n $이지만,

• unbalanced tree 에서는 worst case의 경우 $ h = n $이므로 $ O(n) $의 시간복잡도를 갖는다.