[Data Structure] Binary Search Tree(BST)

트리는 이산수학에서도 다뤘기 때문에 간단히 패스하고 지나간다.
기억을 되새길겸 짚어보자면 Tree는 Acyclic connected graph이다.
그리고 몇가지 특성들을 가지는데 그것은 패쓰~

트리는 트리 자체도 중요하지만 트리의 응용으로 나오는 다른 트리들이 중요하다.
Binary Tree는 각 노드가 차일드 2개를 가지며 left랑 right로 구별되는 트리이다.
Full binary Tree는 모든 leaf의 depth가 같은 트리를 말한다.
Complete Binary Tree는 Full binary tree에서 맨 오른쪽 leaf부터 순서대로 제거된 형태를 띄는 것을 말한다.

그리고 오늘의 주인공 Binary Search Tree는 각 노드 값이 왼쪽 서브트리의 값들보다 크고,
오른쪽 서브트리의 값들보다 작은 것을 말한다. 

삽입과 탐색은 값을 기준으로 노드의 값보다 작으면 왼쪽, 크면 오른쪽으로 연산을 수행하는 것이기 때문에 간단한데
삭제는 약간 까다롭다.

삭제는 헷갈릴 수 있으므로 정리할 겸 한번 적어보자.
슈도코드는 다음과 같다.

bst_remove(root, target)
{
     if ( root->data > target )
          bst_remove( root->left, target );
     else if ( root->data < target )
          bst_remove( root->right, target );
     else if ( root->data == target ){
          if ( root가 left child 없으면 )
              root 없애고 right child를 root로
          else if ( 있으면 )
              bst_remove_max( root->left, root->data );
      }
      else
           // 없음
} 

bst_remove_max(root, data)
{
     if ( root가 right child 없으면 )
         root없애고 left를 root로, data에는 root의 data를
     else
         bst_remove_max( root->right, data );
} 

 
삭제를 함에 있어서 중요한 것은 bst의 정의를 위반해서는 안된다는 것일 것이다.


BST가 삽입과 검색 등에 높은 성능(logarithmic order)을 보여주지만 단점이 있다면
skewed tree형태로 트리가 일자로 생성될 때이다. 또는 지그재그 형태로 트리가 자라날 때이다.
만약 정렬된 데이터를 순서대로 삽입한다면 트리가 한 쪽 방향으로만 자라나게 될 것이고 그런 tree라면 search를 한다 하여도 linear search를 하는 것과 같은 결과가 나올 것이다.

따라서 이러한 문제들을 해결한 Tree를 Balanced Tree라고 한다. Balanced tree는 height 연산도 log의 complexity를 가지도록 한 트리로써 AVL search tree, Red-Black Tree, B-tree 등등이 있다.
이 트리들은 좋은 만큼 복잡한 자료구조이므로 따로 정리하도록 하자.