BST(Binary Search Tree, 이진 탐색 트리)

BST(Binary Search Tree, 이진 탐색 트리)

BST(Binary Search Tree, 이진 탐색 트리)는 이진 탐색 알고리즘을 트리에 적용한 자료구조입니다.

 

이진 탐색 트리의 정의는 다음과 같습니다.

- 노드에 저장된 Key(키)는 유일하다.

- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

이진 탐색 트리의 탐색 연산은 O(log n)의 time complexity를 갖습니다.

이진 탐색 트리의 높이는 log (n + 1)이기 때문입니다.

 

하지만 이진 탐색 트리가 한 쪽으로 편향되어 있다면(Skewed Tree, 편향 트리) time complexity의 worst case가 O(n)이 됩니다.

이를 해결하기 위해 Rebalancing 기법이 등장했습니다.

Rebalancing은 트리 구조를 균형있게 재조정하는 기법입니다.

Red-Black Tree는 이 기법을 구현한 트리입니다.

추후에 살펴보도록 하겠습니다.