Balanced BST

BST에 1, 2, 3, 4, 5, 6, 7 을 넣는다고 생각해보자.

 

1, 2, 3, 4, 5, 6, 7 순서로 값을 추가하면

 

4, 2, 6, 1, 3, 5, 7 순서로 값을 추가하면

 

 

전자의 경우 linked list와 별반 차이가 없다.

 

후자의 경우 탐색에 $O(\log{n})$의 시간이 소요되지만, 전자의 경우 탐색에 $O(n)$의 시간이 소요된다.

 

 

따라서 unbalanced BST보다는 rotation 개념을 이용해 balance를 맞춘 balanced BST가 자주 사용된다.

 

Balanced tree의 예로 AVL tree, red-black tree, splay tree 등이 있다.