Binary Search Tree

상위 문서: Data Structures

개요

해당 문서는 이진 트리(binary tree)의 한 종류인 이진 탐색 트리(binary search tree)에 대해서 다룬다. 먼저, 이진 트리는 루트(root)를 가진 트리 구조이며, 각 노드는 최대 두 개의 자식을 가진다. 이때 자식 노드는 왼쪽(left child)또는 오른쪽(right child)으로 구분된다. 이러한 이진 트리 구조는 figure 1에 잘 나타나 있다. 그 중에서도 이진 탐색 트리는 자료 구조의 한 종류로, 사전(dictionary) 연산(검색, 삽입, 삭제, 최소값, 최대값, 후속자/전임자 찾기)을 효율적으로 수행할 수 있게 한다.

이진 탐색 트리의 중요한 특징은 각 노드 x에 대해 왼쪽 서브 트리의 모든 키 값들은 x보다 작으며, 오른쪽 서브트리의 모든 키 값들은 x보다 크다는 것이다. 이는 figure 1에 잘 나타나 있다. 따라서 어떤 값이든지 "왼쪽으로 갈지, 오른쪽으로 갈지"를 비교를 통해 정할 수 있고, 그 과정에서 원하는 키를 찾을 수 있다. 이는 이진 탐색과 비슷한 원리를 사용하므로, 시간복잡도면에서 효율적이다.

Implementing Binary Search Trees

C언어에서 이진 탐색 트리는 아래와 같이 구현될 수 있다:

typedef struct tree {
    item_type item;       /* 데이터 항목 */
    struct tree *parent;  /* 부모 노드 포인터 */
    struct tree *left;    /* 왼쪽 자식 포인터 */
    struct tree *right;   /* 오른쪽 자식 포인터 */
} tree;

이때 부모 노드에 대한 포인터는 선택 사항이다. 왜냐하면 여러 연산을 구현할 때 순회 과정에서 스택에 부모 노드를 저장하면, 굳이 구조체에 parent 필드를 두지 않아도 되기 때문이다.

Searching in a Binary Tree

이진 탐색 트리에서 특정한 키 값 x를 가진 노드를 찾고자 할 때에는 아래와 같은 코드를 이용한다:

tree *search_tree(struct tree *l, item_type x) {
    if (l == NULL) {
        return(NULL);
    }
    if (l->item == x) {
        return(l);
    }
    if (x < l->item) {
        return(search_tree(l->left, x));
    } else {
        return(search_tree(l->right, x));
    }
}

이는 아래와 같이 작동한다:

1. 현재 노드 l이 NULL이면 탐색 실패 → NULL 반환.
2. 현재 노드의 값이 x와 같으면 탐색 성공 → 해당 노드 반환.
3. x가 현재 노드보다 작으면 왼쪽 서브트리에서 재귀 탐색.
4. x가 더 크면 오른쪽 서브트리에서 재귀 탐색.

즉, 해당 함수는 재귀적으로 작동하며, 이를 통해 시간 복잡도를 추측할 수 있다. 최악의 상황은 x가 존재하지 않아 NULL을 반환할 때까지 함수가 재귀적으로 작동하거나, 트리의 레벨이 가장 높은 leaf 노드에 x 키값이 존재하는 경우이다. 즉, 해당 알고리즘의 시간 복잡도는 트리의 높이인 h에 비례하므로 O(h)이다.
이때 중요한 것은 해당 트리의 모양에 따라 시간 복잡도가 달라진다는 것이다. 만약 트리가 최적으로 구성된 균형 트리라면 $h\approx log(n)$의 시간복잡도를 가진다. 하지만 노드가 최대 하나의 자식만을 가지는 편향 트리라면 $h\approx n$의 시간복잡도를 가진다.

Maximum and Minimum

이진 탐색 트리에서 최솟값/최댓값을 탐색하는 것은 매우 쉽다. 최솟값은 가장 왼쪽에 위치한 노드이며, 최댓값은 가장 오른쪽에 위치한 노드이기 때문이다. 따라서 원리는 같으므로, 최솟값을 탐색하는 코드만 언급한다:

tree *find_minimum(struct tree *t) {
    tree *min;
    if (t == NULL) {
        return(NULL);
    }
    min = t;
    while (min->left != NULL) {
        min = min->left;
    }
    return(min);
}

해당 코드의 원리는 간단하다. 포인터 t가 NULL이면 유효한 이진 탐색 트리가 아니므로 실패한다. 그렇지 않다면 while문을 이용하여 노드의 왼쪽 자식이 없을 때까지 반복하여 내려가고, 최종적으로 가장 왼쪽 노드를 반환한다. 만약 최댓값을 찾고 싶다면, 노드의 오른쪽 자식이 없을 때까지 반복하여 내려가면 된다.

해당 코드의 시간 복잡도는 키값 탐색과 같이 트리의 높이 h에 비례하므로 O(h)이다.