[자료 구조] 이진 탐색 트리

이진 탐색 트리(binary search tree)는 자료 구조의 하나로, 그래프의 트리 구조를 사용합니다. 이진 탐색 트리에서는 각 노드에 데이터가 저장됩니다. - 책 알고리즘 도감

 

1. 이진 탐색 트리의 구조와 특징

이 그림은 이진 탐색 트리의 예입니다. 각 노드에 적혀 있는 숫자가 데이터입니다. 여기에서는 같은 숫자는 존재하지 않는다고 가정하고 설명하겠습니다.

 

 

이진 탐색 트리는 두 가지 특징을 가지고 있습니다. 첫 번째 특징은, 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다는 것입니다. 예를 들어, 노드 9는 그 왼쪽에 있는 가지의 모든 숫자보다 큽니다.

 

 

마찬가지로, 노드 15는 그 왼쪽 가지에 있는 어떤 숫자보다 큽니다.

 

 

 

두 번째 특징은, 모든 노드는 그 노드의 오른쪽 가지에 포함되는 어떤 숫자보다 작은 숫자가 된다는 것입니다. 예를 들어, 노드 15는 그 오른쪽 가지에 있는 어떤 수보다도 작습니다.

 

 

 

이 두 개의 특징으로부터 다음 조건이 성립합니다. 먼저, 이진 탐색 트리의 최소 노드는 최상단에 있는 노드로부터 왼쪽 가지만 계속 따라가면 나오는 가장 끝에 있는 노드(3)가 되고, 반대로 이진 탐색 트리에서 최대 노드는 최상단의 노드로부터 오른쪽 가지만 계속 따라가면 나오는 가장 끝에 있는 노드(28)가 됩니다.

 

 

 

2. 이진 탐색 트리에서 노드를 추가하는 방법

 

예를 들어, 1을 추가한다고 해보겠습니다. 노드 추가 위치를 이진 탐색 트리의 최상단 노드부터 탐색해 갑니다. 추가하려고 하는 1을 현재 노드 값과 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 진행합니다.

 

 

추가 완료

 

 

 

 

 

3. 이진 탐색 트리에서 노드를 삭제하는 방법

예를 들어 28을 삭제하는 경우를 보겠습니다. 28처럼 자식 노드가 없는 노드는 대상 노드만 삭제하면 작업이 끝납니다.

 

 

 

 

23처럼 자식노드가 하나인 노드를 삭제할 때는 대상 노드를 삭제하고 삭제한 노드의 위치로 자식 노드를 이동시키면 끝입니다.

 

 

9처럼 자식 노드가 2개인 경우는 먼저 대상 노드를 삭제하고, 삭제한 노드의 왼쪽 가지에서 최대 노드를 찾아서 삭제한 노드의 위치로 이동시키면 됩니다. (반대로 '오른쪽 가지의 최소 노드'(12)를 삭제한 노드의 위치로 이동시켜도 됩니다.)

 

 

 

4. 이진 탐색 트리에서의 탐색

이진 탐색 트리의 최상단 노드부터 탐색을 시작합니다. 그리고 추가할 때와 마찬가지로 탐색하고자 하는 노드를 현재 노드값과 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 진행하면서 찾으면 됩니다.

 

---

 

<해설>

이진 탐색 트리는 이진 탐색의 개념을 트리 구조로 표현한 것이라 볼 수 있습니다. 데이터를 탐색할 때나 추가할 때의 최적의 위치를 찾을 때, 앞서 본 두 가지 특징을 기준으로 현재 위치의 데이터와 대소를 비교하기만 하면 왼쪽으로 진행하면 좋을지 오른쪽으로 진행하면 좋을지를 알 수 있습니다.

 

이것은 트리의 높이(깊이 또는 단계)만큼만 비교하면 되므로 노드가 n개 있고 트리가 균형 잡힌 경우라면 최대 log2n회의 비교로 이동할 수 있습니다. 따라서 계산 시간은 O(log n)이 됩니다. 단, 트리가 한쪽으로 치우쳐서 직선에 가까운 모양인 경우에는 트리가 높아져서 O(n)이 될 수도 있습니다.

 

 

<보충>

이진 탐색 트리를 확장한 자료 구조는 여러 개가 있습니다. 예를 들어, 트리가 한쪽으로 치우친 경우 모양을 바로잡기 위해 항상 균형을 유지하도록 하는 구조도 있습니다. 이것을 '자가 균형 이진 탐색 트리(self-balancing binary search tree)'라고 하며, 탐색 효율을 유지할 수 있습니다. 또한, 여기서 소개한 이진 탐색 트리에서는 하나의 노드가 가질 수 있는 자식 노드가 최대 두 개였지만, 이것을 m개(m은 미리 정해둔 상수)로 확장해서 자식 수에 제한을 두지 않고 트리의 균형을 도모한 'B 트리'라는 것이 있습니다.

 

참고 - 책 알고리즘 도감