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 등이 있다.
'CS > 자료구조' 카테고리의 다른 글
AVL Tree (0) | 2022.04.19 |
---|---|
Tree rotation (0) | 2022.04.18 |
Binary Search Tree (BST) (0) | 2022.04.18 |
Max Heap (0) | 2022.04.18 |
Tree (Introduction) (0) | 2022.04.18 |