06. 자료구조론 - 이진탐색트리 (Binary Search Tree)

이진탐색트리 (BST)

이진탐색트리는 이진트리의 일종으로, 트리의 노드들을 일정한 기준으로 정렬해놓아서 트리 내에서 원하는 노드를 쉽게 찾을 수 있도록 한 트리입니다. 

이진탐색트리는 다음과 같은 특징을 갖습니다.

트리 내의 모든 노드X에 대해서
1. X의 왼쪽 subtree에 있는 모든 값들은 X보다 작고,
2. X의 오른쪽 subtree에 있는 모든 값들은 X보다 크다.
3. 트리 내의 모든 노드의 값은 중복되지 않는다.

따라서 이진탐색트리에서 어떤 subtree를 떼어내더라도 그또한 이진탐색트리가 됩니다. 

이진탐색트리에서 탐색을 빠르게 할 수 있다고 하였는데, 이에 앞서 linear array에서의 탐색에 대해 알아보겠습니다.

• 순차탐색 : 일반배열에 값을 정렬하지 않고 그냥 저장해놓고, 원하는 값을 찾을 때는 순차적으로 앞에서부터 하나하나 봐가면서 탐색을 한다면, Insert에는 O(1) 만큼이 들고, Find에는 O(n) 만큼의 시간복잡도가 들게됩니다.
• 이진탐색 : 일반배열에 값을 정렬해서 저장해두고, 원하는 값을 찾을 때 이진탐색 (Binary search)를 이용한다면, insert에는 O(n)만큼이, search에는 O(log n)만큼의 시간복잡도가 필요합니다. 

구현

이진탐색트리에서 노드에 대한 구조체는 다음과 같이 구현할 수 있습니다.

typedef struct _Node* BinarySearchTree;
typedef struct _Node {
    int element;
    BinarySearchTree left;
    BinarySearchTree right;
} Node;

Find

Node* Find(BinarySearchTree tree, int x) {
    if (tree == NULL) return NULL;
    else if (x < tree->element) return Find(tree->left, x);
    else if (x > tree->element) return Find(tree->right, x);

    return tree; // x == tree->element
}

찾고자하는 값과 현재 보고있는 트리의 루트노드의 값을 비교해서 찾는 값이 더 작으면 왼쪽트리에서, 찾는 값이 더 크면 오른쪽 트리에서 찾도록 재귀적으로 find를 구현할 수 있습니다.

오른쪽과 같이 찾는 값이 없으면 Find(NULL, x)를 호출하고, if (tree == NULL) 조건에 걸려 최종적으로 NULL이 리턴되게 됩니다. 

Insert

BinarySearchTree Insert(BinarySearchTree tree, int x) {
    if (tree == NULL) {
        // 트리의 첫 노드이므로 트리를 새로 만들고 초기화해주어야함
        tree = (BinarySearchTree) malloc(sizeof(Node));
        if (tree == NULL) {
            // do something for out of space error
            return NULL;
        }
        tree->element = x;
        tree->left = tree->right = NULL;
    } else if (x < tree->element) {
        tree->left = Insert(tree->left, x);
    } else if (x > tree->element) {
        tree->right = Insert(tree->right, x);
    }

    // 만약 x == tree->element이면 이미 x가 트리에 존재하는 것이므로 아무것도 할 필요가 없음
    return tree;
}

삽입도 탐색과 마찬가지로 분할정복을 사용하여 재귀적으로 구현할 수 있습니다.

만약 tree가 NULL이라면 새롭게 노드를 만들어줍니다. 

만약 삽입하고자하는 값이 루트노드(tree)의 값보다 작다면, 새로운 값은 트리의 왼쪽 subtree에 삽입될 것이므로 Insert(tree->left, x)를 통해 왼쪽 서브트리에 x를 삽입해주도록하고, 해당 함수에서 리턴된 서브트리(이제는 x가 추가적으로 삽입된 트리)가 tree->left에 들어가도록 해줍니다.

반대의 경우도 동일한 방식으로 구현할 수 있습니다.

이진탐색트리에서는 값의 중복을 허용하지 않으므로 x가 이미 트리에 존재한다면 아무것도 하지않고 동일한 트리를 그대로 리턴해줍니다.

트리의 노드를 가리키는 포인터를 <노드 안의 값>으로 표현하겠습니다. (예를 들어 위 트리의 루트노드는 <8>이라고 표현하겠습니다.)

위과 같은 트리에 7을 삽입한다고하면, 우선 Insert(<8>, 7)이 호출됩니다.

7은 8보다 작으므로 왼쪽트리에 값을 삽입해야하고, 따라서 Insert(<3>, 7)이 호출됩니다.

7은 3보다 크므로 <3>의 오른쪽 트리에 값을 삽입해야하고, Insert(<5>, 7)이 호출됩니다.

7은 5보다 크므로 <5>의 오른쪽 트리에 값이 삽입되어야하고, <5>의 오른쪽 서브트리는 없으므로 Insert(NULL, 7)이 호출됩니다. 

그러면 7을 위한 새로운 노드가 할당되고 호출된 함수들이 차례차례 리턴되면서 <8>, <3>, <5> 노드의 left혹은 right가 7을 포함한 새로운 트리로 갱신됩니다.

Delete

이진탐색트리에서 값을 삭제하는 작업은 삭제할 노드의 위치에 따라 상황이 달라집니다.

1. 삭제할 노드가 leaf 노드인 경우

가장 간단한 경우입니다.

삭제할 노드의 부모 노드를 찾아 삭제할 노드쪽의 subtree를 가리키는 포인터를 NULL로 변경하면 됩니다. 

2. 삭제할 노드에 하나의 자식노드가 있는 경우 

해당 자식노드를 삭제할 노드의 부모노드에 연결해주면됩니다.

3. 삭제할 노드에 두개의 자식노드가 있는 경우

가장 복잡한 경우입니다. 아래 두가지 방법 중 아무 방법으로나 구현할 수 있습니다.

1) 오른쪽 서브트리에서 가장 작은 값을 갖는 노드로 삭제할 노드를 대체한다.

2) 왼쪽 서브트리에서 가장 큰 값을 갖는 노드로 삭제할 노드를 대체한다.

 

BST에서 최솟값, 최댓값을 찾는 코드는 다음과 같습니다.

Node* FindMin(BinarySearchTree tree) {
    if (tree == NULL) return NULL;
    else if (tree->left == NULL) return tree;
    return FindMin(tree->left);
}

Node* FindMax(BinarySearchTree tree) {
    if (tree == NULL) return NULL;
    else if (tree->right == NULL) return tree;
    return FindMin(tree->right);
}

최솟값은 계속 트리의 왼쪽을 따라, 최댓값은 계속 트리의 오른쪽을 따라가서 가장 끝에 있는 노드를 리턴하면됩니다.

BinarySearchTree Delete(BinarySearchTree tree, int x) {
    Node* tmp;
    if (tree == NULL) {
        // 삭제하고자하는 값이 트리에 존재하지 않는 경우
        return NULL;
    } else if (x < tree->element) {
        tree->left = Delete(tree->left, x);
    } else if (x > tree->element) {
        tree->right = Delete(tree->right, x);
    } else if (tree->left && tree->right) {
    	// 자식노드가 두개 있는 경우
        // 오른쪽 서브트리에서 최솟값을 찾아 삭제할 노드를 대체하고 
        tmp = FindMin(tree->right);
        tree->element = tmp->element;
        // 해당 최솟값은 오른쪽 서브트리에서 삭제함
        tree->right = Delete(tree->right, tree->element);
    } else {
    	// 자식노드가 없거나 1개만 있는 경우
        tmp = tree;
        if (tree->left == NULL) {
            tree = tree->right;
        } else {
            tree = tree->left;
        }
        free(tmp);
    }
    return tree;
}

Analysis of BST

이진탐색트리에서 find, insert, delete의 시간복잡도는 트리의 height에 비례하여 커집니다.

왼쪽과 같이 Complete Binary Tree인 경우가 Best case로, 노드의 개수가 N개일 때 트리의 height는 $log(N)$에 비례하게 됩니다. -> $O(log N)$

오른쪽과 같이 노드들이 일직선으로 연결된 경우가 최악의 케이스로, 노드의 개수가 N개일 때, height는 $N$에 비례하게 됩니다. -> $O(N)$

 

그러면 평균적인 시간복잡도 혹은 평균적인 height는 어떻게 될까요?

이는 Internal Path Length를 통하여 구할 수 있습니다.

Internal Path Length는 N개의 노드를 갖는 이진탐색트리에서 모든 노드의 depth의 합을 의미합니다.

그리고 결론부터 얘기하자면 이진탐색트리에서 평균적인 Internal Path Length는 $O(NlogN)$이 됩니다.

그리고 이를 N으로 나누면 평균적인 height는 $O(logN)$이 됩니다.

 

이를 증명하자면 다음과 같습니다.

- D(N) 은 N개의 노드를 갖는 트리의 Internal Path Length입니다.
- N개의 노드를 갖는 트리를 [루트노드]와 [i개의 노드를 갖는 왼쪽 서브트리], [(N-i-1) 개의 노드를 갖는 오른쪽 서브트리]로 나눠 생각할 수 있습니다.
- D(i)와 D(N-i-1)을 왼쪽과 오른쪽 서브트리의 Internal path length라고 할 수 있습니다.

- $D(N) = D(i) + D(N-i-1) + N-1$ 이라고 할 수 있습니다.
여기서 + N-1의 의미는 N개의 노드를 갖는 트리의 루트노드에서 왼쪽, 오른쪽 서브트리로 가는 edge를 서브트리의 모든 노드(N-1개)에 대해서 더해준 것입니다.
그리고 D(i) 나 D(N-i-1)의 평균적인 값은 모두 ${1\over N} \sum_{i=0}^{N-1}{D(i)}$ 이라고 할 수 있습니다.
따라서 $D(N) = {2\over N} \sum_{i=0}^{N-1}{D(j)} + N-1$ 이 됩니다.

그러면 귀류법을 통해 $D(n) \le 4nlogn$ 임을 증명해봅시다.
우선 $D(1) = 0$ 임을 알고있습니다.
그리고 위의 가설이 $1 \leq n \leq k-1$에 대해 성립한다고 가정해봅시다. 그러면
$$
D(k) = {2\over k}[\sum_{i=1}^{k-1}{D(i)}] + k-1\\
\leq {2\over k}[\sum_{i=1}^{k-1}{4i \log i}] + k-1\\
= {8\over k}[\sum_{i=1}^{k-1}{i \log i}] + k-1\\
\leq {8\over k}[{\sum_{i=1}^{\lceil {k\over 2} \rceil -1}{i \log({k\over 2}}} + \sum_{i=\lceil {k\over 2} \rceil}^{k-1}{i \log k}] + k-1\\
\leq {8\over k} [{{k^2}\over 2}log k - {{k^2}\over 8}] + k-1\\
=4k log k - 1 \leq 4k log k
$$
이 되어 증명이 완료됩니다.