이진 탐색 트리 (Binary Search Tree)

원래 계획은 레드 블랙 트리를 설명하는 거였는데, 그걸 설명하려면 이진 탐색 트리부터 설명해나가는 것이 더 좋다고 생각되어 여기부터 써 봅니다.

 

개요

아래와 같은 특성을 가지는 추상적 자료형(Abstract Data Type)을 생각해봅시다.

  1. 정렬 가능한 데이터의 집합에서
  2. 검색, 삽입, 삭제 연산을
  3. 빠르게 할 수 있다.

여기서 중요한 것이 정렬 가능검색 연산입니다. 먼저 정렬 가능성을 언급한 이유는 기본적으로 정렬된 데이터는 이진 탐색으로 빠르게 검색 가능하기 때문입니다. 또 임의의 데이터가 이 집합에 있는지 빠르게 확인할 수 있다는 점에서 위 추상적 자료형은 데이터베이스에 아주 적합한 구조라고 할 수 있습니다. 이걸 어떻게 구현할까요? 단순히 연결 리스트로 구현하면 검색하는 데 $O(n)$만큼 걸릴 것이고, 정렬된 연결 리스트로 구현하더라도 삽입, 삭제는 $O(n)$이 걸릴 겁니다. ($n$은 원소의 개수) 결국 단순한 리스트로는 구현 못 한다는 거죠.

일단 을 생각해봅시다. 힙도 아주 비슷한 성질을 가집니다.

  1. 정렬 가능한 데이터의 집합에서
  2. 최솟값 검색, 삽입, 최솟값 삭제 연산을
  3. 빠르게 할 수 있다.

이 성질을 가지는 추상적 자료형 역시 단순한 리스트로는 $O(n)$보다 빠르게 구현할 수 없기 때문에 힙 성질을 만족하는 트리를 이용해서 구현하죠. 따라서 빠른 속도를 위해 여기서도 힙과 비슷하게 트리를 사용합니다. 이 트리는 이진 탐색 트리라고 하며, 정의는 다음과 같습니다.

  1. 이진 트리이다.
  2. 각 노드는 키(key)를 가진다.
  3. 어떤 노드 $v$의 왼쪽 서브트리에 있는 모든 노드는 $v$보다 키가 작고, 오른쪽 서브트리에 있는 모든 노드는 $v$보다 키가 크다.

일단 중복을 허용하지 않는다고 가정하겠습니다. (즉, 데이터의 집합에 같은 값은 있을 수 없습니다.) 정의에 따라, 이진 탐색 트리는 아래 성질을 자연히 만족하게 됩니다.

  1. 제일 왼쪽 노드는 최솟값을 가집니다.
  2. 제일 오른쪽 노드는 최댓값을 가집니다.
  3. 이진 탐색 트리를 중위 순회하면 트리가 가지는 모든 키들을 크기 순서대로 늘어놓을 수 있습니다.

아래는 1, 2, 3, 4, 6, 7, 8, 10, 15를 포함하는 이진 탐색 트리의 예입니다. 앞으로의 예시는 이 트리로 들겠습니다.

여기서 NIL은 자식이 없다는 것을 의미하는 가상의 리프 노드입니다. 실제 구현시 NIL을 구현해서 연결시켜주는 경우도 있고, 그냥 자식 노드를 가리키는 포인터를 NULL로 하는 경우도 있습니다.

 

검색

이진 탐색 트리의 성질에 의해 이분 탐색을 그대로 쓸 수 있습니다. 트리에서 어떤 값을 찾고자 하면

  1. 루트에 찾는 값이 있으면 찾는 데 성공입니다.
  2. 루트의 키보다 찾는 값이 작으면 왼쪽 서브트리로 내려갑니다.
  3. 찾는 값이 더 크면 오른쪽 서브트리로 내려갑니다.

만약 NIL에 도달하면 찾는 값이 없는 겁니다. 위 이진 탐색 트리에서 7을 찾는 경우를 예로 들어봅시다.

한편 12를 찾는 경우에는

가 되어 NIL에 도달하므로 12는 이 트리에 없다고 할 수 있습니다.

시간 복잡도는 트리의 높이, 즉 루트에서 를 $h$라 할 때 $O(h)$가 됩니다.

 

삽입

새로운 값의 삽입은 항상 NIL의 위치에서만 일어납니다. 먼저 검색을 하고, 이미 있는 값이 아니라면 그렇게 도달한 NIL의 위치에 새로운 값을 집어넣습니다. 12를 추가한다고 하면

위 그림과 비교하면 NIL의 위치에 12가 들어갔다는 걸 확실히 알 수 있습니다. 역시 시간 복잡도는 $O(h)$입니다.

 

삭제

노드의 삭제는 상대적으로 복잡합니다. 무턱대고 삭제하다간 이진 탐색 트리가 지켜야 할 성질이 깨지기 때문이죠. 삭제는 크게 세 가지 경우로 나눌 수 있습니다.

자식이 없는 경우

단순히 노드를 지우고 그 자리를 NIL로 대체하면 됩니다.

자식이 하나만 있는 경우

삭제할 노드의 부모와 자식을 서로 이어주면 됩니다. 예를 들어 15를 삭제한다고 하면 15의 부모인 8을 15의 자식인 10과 연결해주고 15를 삭제합니다.

자식이 둘인 경우

이 경우가 복잡합니다. 먼저 삭제할 키 다음으로 큰 키를 가진 노드를 찾아야 합니다. 4를 삭제하는 경우를 예로 들어 설명하겠습니다. 첫 번째로 4 다음으로 큰 값인 6을 가진 노드를 찾습니다. 그리고 찾은 노드의 키를 삭제할 노드에 복사합니다.

찾은 노드의 키 6은 삭제할 키 4보다 큰 키 중에 제일 작은 키죠. 4보다 큰 키는 4의 오른쪽 서브트리에 모두 모여 있으므로 6은 4의 오른쪽 서브트리에 있는 값 중 최솟값이 됩니다. 또한 4의 왼쪽 서브트리에 있는 값은 4보다 작고, 따라서 당연히 6보다 작습니다. 결과적으로 4가 있던 위치에 6을 넣어도 여전히 이진 탐색 트리의 성질은 깨지지 않습니다. (물론, 중복을 허용하면요.)

그리고 원래 6을 지워줍니다. 이 6은 절대 왼쪽 자식을 가질 수 없습니다. 만약 왼쪽 자식이 있으면, 왼쪽 자식은 6보다 크고 (6의 왼쪽 서브트리에 있으므로) 4보다 작기 때문에 (4의 오른쪽 서브트리에 있으므로) 4 다음으로 큰 값이 6이라는 가정에 어긋납니다. 고로 자식이 없거나 하나만 있는 경우를 처리하는 방법으로 6을 삭제할 수 있습니다.

그럼 6을 찾는 게 관건인데, 6이 4의 오른쪽 서브트리에서 최솟값이기 때문에 오른쪽 서브트리에서 제일 왼쪽에 있게 됩니다. 즉, 삭제할 노드에서 오른쪽 자식으로 내려간 다음, 왼쪽 자식이 없을 때까지 왼쪽 자식으로 내려가면 찾을 수 있습니다.

삭제할 키 다음으로 큰 키를 찾는 과정이 있으므로 역시 시간복잡도는 $O(h)$입니다.

 

이진 탐색 트리의 단점

위에서 보듯, 이진 탐색 트리 연산의 시간복잡도는 트리 높이 $h$에 비례합니다. 트리가 충분히 균형잡혀 있다면 $h=O(\log n)$이 되어 아주 빠르게 연산할 수 있지만 다음과 같이 똑같이 1, 2, 3, 4, 6, 7, 8, 10, 15를 포함하고 있어도 한 쪽으로 치우친(skewed) 경우에는 정렬된 연결 리스트와 다를 게 없습니다. 결국 평균적으로는 $O(n)$보다 빠를지 몰라도 최악의 경우엔 정렬된 연결 리스트와 동일한 성능을 보여줍니다.

이걸 해결하기 위해 이진 탐색 트리에 몇가지 속성을 더하여 균형잡힌 이진 트리가 되도록 한 자료구조들이 있습니다. 이에 관해서는 다음 글들에서 살펴보겠습니다.