이진 탐색 트리와 균형 이진 트리

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 현재 노드보다 작은 값이고 오른쪽 자식은 현재 노드보다 큰 값을 가지는 이진 트리이다.

 

이진 탐색을 이용하면 시간복잡도 O(logn) 으로 빠른 탐색이 가능하다. 그런데 이러한 이진 탐색을 위한 저장공간이 배열이기 때문에 (인덱스가 있어야한다) 결국 이 배열에 삽입/삭제 시에는 O(n) 의 시간복잡도를 가지게 된다.

 

탐색, 삽입, 삭제 에 전부 O(logn) 가지는 자료구조를 표현한 것이 이진 탐색 트리이다.

 

이진 탐색 트리의 순회 탐색에는 3가지 방법이 있다.

전위 순회

1. 입력으로 들어온 현재 노드를 출력
2. 왼쪽 노드 방문
3. 오른쪽 노드 방문

중위 순회

1. 왼쪽 노드를 방문
2. 현재 노드를 출력
3. 오른쪽 노드를 방문

후위 순회

1. 왼쪽 노드 방문
2. 오른쪽 노드 방문
3. 현재 노드 출력

이진 탐색 트리의 단점은 루트 노드의 값 보다 계속 크거나 작은 값이 자식 노드로 들어오면 해당 이진 탐색 트리는 log(n) 의 시간 복잡도를 가질 수 없다는 것이다.

이를 방지하기 위해 균형 잡힌 트리가 필요하다.

균형 잡힌 트리는 트리의 깊이를 최소화하여 탐색, 삽입, 삭제 작업을 보다 효율적으로 수행할 수 있는 트리 구조를 말한다. 대표적인 균형 잡힌 트리로는 AVL 트리, 레드-블랙 트리, B 트리 등이 있다.