이진 탐색 트리

 이진 탐색 트리(Binary Search Tree, BST)란 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다.

 이 트리의 가장 훌룡한 점은 탐색 시 시간 복잡도가 O(log n)라는 점이다.

 

이진 탐색 트리를 이용해 원하는 값을 찾는 방식

 

 BST는 랜덤하게 생성해도 대부분의 경우 균형이 잘 맞는 아름다운 형태로 트리를 표현할 수 있지만, 운이 나쁘면 트리의 모양이 균형을 제대로 이루지 못할 수 있다. 균형이 많이 깨지면 탐색 시에 O(log n)이 아니라 O(n)에 근접한 시간이 소요될 수 있다.

균형이 깨진 이진 탐색 트리

 이런 트리는 균형을 맞춰 줄 필요가 있는데 그래서 고안해낸 것이 바로 '자가 균형 이진 탐색 트리'다.

 

 자가 균형 이진 탐색 트리

 자가 균형(또는 높이 균형) 이진 탐색 트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리다.

  균형이 잘 잡힌 트리를 나타낸 그림 2)는 루트의 높이가 3으로, 높이를 가능한 한 작게 유지한 트리임을 확인할 수 있다.