이진 탐색 트리란?

오늘은 탐색 알고리즘 중 이진 탐색 알고리즘과 비슷한 이름을 가진 알고리즘인 이진 탐색 트리에 대해 알아보려고 한다

참고로 이진 탐색 트리는 이진 탐색 알고리즘의 원리를 트리 형태로 확장한 자료구조로 이진 탐색이 배열 위에서 이루어진다면 이진 탐색 트리는 트리 구조 위에서 탐색을 진행 할 수 있다

이진 탐색 트리란?

이진 탐색 트리는 이진 트리의 한 형태로서 각 노드의 특성에 따라 위치가 정해지며 이진 탐색 트리는 다음과 같은 세 가지 특징을 갖고 있다

1. 모든 노드는 유일한 키를 갖는다
2. 왼쪽 서브트리(자식 트리)의 키들은 그 루트의 키보다 작다
3. 오른쪽 서브트리의 키들은 그 루트의 키보다 크다.

이러한 특징들 가진 덕분에 이진 탐색 트리에서는 효율적인 탐색 작업을 수행할 수 있다

이진 탐색 트리의 작동 방식

이진 탐색 트리에서의 탐색, 삽입, 삭제 작업은 위에서 살펴본 특징들에서 유추할 수 있듯이 굉장히 직관적인데

글로만 보면 잘 이해가 안될 수 있으니 예를 들어 15를 찾는 상황을 가정했을 때

주어진 트리:

        10
       /  \
      5    20
          /  \
        15    25

첫 번째 진행:

루트 값인 10과 15를 비교 -> 15가 더 크니 오른쪽 자식 노드로 이동

두 번째 진행:

20과 15를 비교 -> 15가 더 작으니 왼쪽 자식 노드로 이동

세 번째 진행:

15와 15를 비교 -> 일치하니 탐색 종료

이와 같은 과정을 통해서 이진 탐색 트리는 노드의 추가, 삭제, 탐색을 진행한다

이진 탐색 트리의 장단점

마지막으로 이진 탐색 트리에 장단점을 알아보자

장점:

1. 이진 탐색과 같은 O(log N)의 시간 복잡도를 가진다
2. 구조가 단순하고 구현이 비교적 용이하다
3. 탐색, 삽입, 삭제의 연산이 평균적으로 빠르다

단점:

1. 트리가 균형이 맞지 않을 경우 최악의 성능을 보일 수 있다 (이를 해결하기 위한 여러 변형된 트리 형태들이 있음 예: AVL 트리, 레드-블랙 트리 등)
2. 구현이 배열에 비해 약간 복잡하다