이진탐색트리(Binary Search Tree)

이진탐색트리는 이름에서 알 수 있듯이 자식노드를 최대 2개까지만 가지는 이진트리의 특성을 가지고 있으며 다음과 같은 조건을 만족한다.

1. 어떤 노드 V를 기준으로 왼쪽 서브트리의 모든 키값은 V보다 작아야 한다.

2. 어떤 노드 V를 기준으로 오른쪽 서브트리의 모든 키값은 V보다 커야 한다.

3. 각 노드의 키값은 유일해야 한다.

아래 트리는 이진탐색트리의 모든 조건을 만족한다.

이진탐색트리를 중위순회로 방문하면 오름차순으로 정렬된 값을 얻을 수 있다.

1, 2, 4, 6, 8, 9

탐색

이진탐색트리는 그 이름에 '탐색'이 있듯 탐색이 효율적이다.

위의 이진탐색트리에서 8을 탐색해보자

우선 루트노드 6을 8과 비교했을 때 8은 6의 오른쪽 서브트리에 존재할 것이기 때문에 왼쪽 서브트리는 탐색할 필요가 없다.

다음으로 오른쪽 서브트리의 루트노드인 9를 8과 비교하면 8은 9보다 작기 때문에 9의 왼쪽 서브트리로 내려간다.

9의 왼쪽 서브트리에 우리가 찾고자 하는 8을 찾았다.

만약 위의 이진탐색트리에서 3을 찾고자 한다면

6, 2, 4를 거쳐 3이 존재하지 않는다는 것을 알 수 있다.

즉 이진탐색트리에서 탐색연산의 시간복잡도는 트리의 높이인 O(h)가 된다.

최악의 경우 Leaf노드까지 탐색하게 되기 때문이다.

삽입

이진탐색트리의 삽입은 탐색을 통해 데이터가 들어갈 자리를 찾아 삽입된다.

아래 트리에서 5를 삽입할 것이다.

이진탐색트리의 삽입 연산은 탐색을 통해 이루어지기 때문에 탐색과 마찬가지로 O(h)의 시간복잡도를 갖게 된다.

또한 삽입은 항상 Leaf 노드에서 이루어지며 트리의 최소값과 최대값은 트리의 가장 왼쪽, 오른쪽이 된다.

삭제

이진탐색트리에서 삭제연산은 원하는 노드를 탐색한 뒤 해당 노드를 삭제한다.

이때 이진탐색트리의 구조가 깨질 수 있으므로 삭제 후 기존노드를 이진탐색트리의 조건에 맞게 조정해야 한다.

이진탐색트리의 삭제 연산은 3가지 케이스로 나눌 수 있다.

(1) 삭제하려는 노드의 자식노드가 존재하지 않는 경우

바로 삭제가 가능하다.

아래 이진탐색트리에서 8을 삭제한다고 했을 때 루트노드부터 탐색하여 8을 찾는다. 8은 자식노드가 존재하지 않으므로 바로 삭제할 수 있다.

(2) 삭제하려는 노드의 자식노드가 1개만 있는 경우

해당 노드를 삭제하고 해당 노드의 자식노드와 부모노드를 연결시켜준다.

아래 이진탐색트리에서 11을 삭제하려고 할 때, 11은 자식노드가 1개만 있는 경우이므로 11을 삭제하고 9와 14를 연결시켜준다.

14를 루트로 하는 서브트리의 모든 키값은 9보다 크기 때문에 그냥 연결해도 이진탐색트리의 조건에 위배되지 않는다.

자식노드가 1개인 경우엔 다음과 같은 경우에도 삭제 후 연결시켰을 때 아무런 문제가 없다.

11을 삭제할 것이다.

(3) 삭제하려는 노드의 자식노드가 2개인 경우

해당 노드를 삭제하고 해당 노드의 predecessor(왼쪽 서브트리의 최대값) 또는 successor(오른쪽 서브트리의 최소값)로 대체한다.

predecessor와 successor는 자식노드가 존재하지 않거나 자식노드가 하나만 존재한다.

아래 이진탐색트리에서 9를 삭제할 것이다.

여기서 삭제될 9의 위치에 올 수 있는 노드는 predecessor인 8과 successor인 10이 된다.

8은 9의 왼쪽 서브트리에서 최대값이며 10은 9의 오른쪽 서브트리에서 최소값이기 때문이다.

9를 삭제하고 predecessor인 8을 9의 자리로 옮겼을 때 결과는 아래와 같다.

predecessor인 8은 자식노드가 존재하지 않았기 때문에 9의 위치에 8을 놓고 기존 8의 위치에 있는 노드는 삭제한다.

9를 삭제하고 successor인 10을 옮기는 경우를 보자

이와 같은 결과를 갖게 될 것이다.

여기서 눈여겨 볼 점은 처음에 삭제할 노드 9를 기준으로 successor였던 10은 자식노드를 1개 가지고 있다는 점이다.

이는 자식노드가 1개만 존재하는 삭제연산 두번째 케이스에 해당된다. 따라서 기존 successor 10의 자식노드인 13과 successor 10의 부모노드인 14를 연결시킨 것이고 이진탐색트리의 조건에 위배되지 않는다. 

자식노드가 1개인 predecessor를 옮기는 경우도 마찬가지다.

만약 successor 10이 13이라는 자식노드를 가지고 있지 않았다면 자식노드가 존재하지 않았던 predecessor 8을 옮기는 경우와 같다.

이진탐색트리의 문제점

이진탐색트리는 탐색, 삽입, 삭제의 시간복잡도가 O(h)가 된다. 즉 트리의 height에 따라 수행시간이 결정된다.

그러나 이진탐색트리의 조건을 만족함에도 불구하고 문제가 되는 경우가 존재한다.

아래는 이진탐색트리이다.

이 이진탐색트리는 노드가 6개지만 높이는 3이 된다.

아래 이진탐색트리는 위의 트리와 같은 노드의 수, 같은 키값을 가진다.

하지만 이 이진탐색트리는 높이가 2이다. 전자보다 높이가 낮으며 균형이 잘 잡혀있다.

만약 이진탐색트리가 극단적인 구조를 가지게 될 경우 한 쪽으로만 계속 늘어지는 구조를 가지게 될 것이다.

이런 경우 시간복잡도는 O(n)이 될 것이다.

이러한 문제를 해결한 것이 AVL 트리이다.

AVL 트리는 이진탐색트리의 장점을 살리면서 균형이 깨진다는 단점을 해결하였다.