이진 탐색 트리

이진 트리는 정렬 여부와 관계없이 모든 노드가 둘 이하의 자식을 갖는 단순한 트리 형태를 말했다. 그렇다면 이진 탐색 트리(BST) 란 무엇일까?

이진 탐색트리란 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어 있는 트리를 뜻한다. 이렇게 왼쪽과 오른쪽의 값들이각각 값의 크기에 따라 정렬되어 있는 트리를 이진탐색트리라 한다. 이 트리의 가장 훌륭한 점은 탐색시 시간 복잡도가 O(log n)이라는 것이다.

8을 찾는 법

이진탐색트리를 이용해 숫자 8을 찾는 과정을 확인해보자. 이 그림에서 루트는 15이며 8은 15보다 작다. 따라서 왼쪽 자식 노드를 탐색한다. 10 또한 8보다 크기 때문에 왼쪽 노드로 이동한다. 5은 8보다 작기 때문에 오른쪽 7은 8보다 크기 때문에 오른쪽으로 이동한다. 따라서 이렇게 쉽게 값을 찾을 수 있다. 만약 6을 찾고자 하면 5에서 오른쪽 노드로 7에서 왼쪽 노드로 이동해야 하는데 왼쪽 노드가 없으므로 '정답 없음' 을 출력 하게 된다. 

 

균형이 잘 맞는 트리에서는 상당히 빠른 탐색시간을 보여주는 BST이지만 균형이 잘 맞지 않는 경우는 O(n)의 탐색시간을 보여주기도 한다. 

균형이 깨진 이진 탐색 트리

이렇게 될 경우 연결 리스트와 다르지 않다. 7을 찾기 위해서는 루트부터 맨 끝까지 차례대로 모두 탐색해야 하므로 전혀 효율적이지 않은 트리가 된다. 강력한 로그 계산을 기반으로 하는 이진 탐색 트리의 장점을 전혀 살 릴 수 없다. 따라서 이진 트리는 균형을 맞춰 줄 필요가 있다. 그래서 고안해낸것이 바로 '자가 균형 이진 탐색 트리'다.

 

자가 균형 이진 탐색 트리

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

 

자가 균형 이진 탐색 트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 즉 높이를 가능한 낮게 유지하는 것이 중요하다는 얘기다. 다음 그림과 같이 불균형꽈 균형의 차이는 크게 높이로 구분 할 수 있다. 기존의 균형 트리와 비교해보면 

불균형 트리와 균형 트리

만약 7을 찾는 경우라면 1번 경우라면 7번의 연산이 실행되어야 하지만 2의 경우에는 불과 두번 만에 7을 찾는게 가능하다. 극단적인 경우로 100만개의 아이템이 있는데 가장 끝에 위치한 아이템을 찾기 위해서 1번은 100만번의 연산이 필요하지만 2의 경우에는 최대 19번(log2 100000000)이면 어떤 값이는 찾아낼 수 있다. 

이처럼 불균형과 균형의 서능차이느 꽤 크다. 대표적인 형태로는 AVL 트리와 레드-블랙 트리 등이 있다.