BST(Binary Search Tree)

이진탐색트리

• 정렬된 트리, 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, right subtree에는 그 node의 값보다 큰 값들을 지는 node들로만 이루어져 있는 binary tree

Binary Tree

• 모든 node의 child nodes의 갯수가 2 이하인 트리

BST 조건

1. root node의 값보다 작은 값은 left subtree, 큰 값은 right subtree
2. subtree도 1번 조건을 만족(Recursive)
   

search $O(logn)$

worst case

균형이 많이 깨져서 한 쪽으로 치우친 BST의 경우, Linked list 처럼 되기 때문에 탐색 시 시간복잡도는 O(n)

해결방법

자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지, 대표적으로 AVL트리와 Red-Black tree