[자료구조] 이진탐색트리(binary search tree)

이진탐색트리: 이진트리를 정렬하여 노드 탐색 시간을 줄여준다. 이진트리의 특성을 모두 가진다. 

 

정렬방식은 smaller to the left, larger to the right

 

 

 

이진 탐색 트리의 평균 시간 복잡도는 O(log2n)이다.

하지만, 최악의 경우 이진탐색트리의 모양이 아래와 같이 만들어 질 수 도 있다. 이 경우 시간 복잡도는 O(n)이다.

 

노드의 탐색시간을 더 줄이기 위해 등장한 것이 height-balanced binary search tree이다. 즉, 왼쪽과 오른쪽 subtree의 균형을 맞혀주어서 트리의 높이를 최대한 줄이는 것이다. 트리의 높이가 높을 수록 탐색시간이 길어지기 때문이다. 

height-balanced binary search tree의 예로는 AVL tree, T-Tree, 2-3 tree, Red-Black tree 등이 있다.