4-2. 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리란?

 이진 트리에 삽입, 삭제 규칙을 가미하여 탐색에 용이하도록 구성된 트리이다. 

 

이진 탐색 트리의 규칙

이진 탐색 트리의 예시. 왼쪽 자식은 부모보다 항상 작고, 오른쪽 자식은 크다.

 

이진 트리는 다음과 같은 규칙을 가지고 있다.

 

 1. 모든 노드의 값은 유일하다.

 2. 오른쪽 자식 노드의 값이 왼쪽 자식 노드보다 항상 크다.

 

이진 탐색 트리의 연산

 각 예시 코드에 쓰이는 트리 노드의 구조체는 이전 공부 기록을 참조.

 2024.07.07 - [전산/자료구조] - 4-1. 이진 트리 (Binary Tree)

 

 삽입

// 새로운 노드를 삽입하는 함수
struct Node* insert(struct Node* node, int key) {
    // 트리가 비어있으면 새 노드를 반환
    if (node == NULL) {
        return newNode(key);
    }

    // 키가 노드보다 작으면 왼쪽 서브트리에 삽입
    if (key < node->key) {
        node->left = insert(node->left, key);
    }
    // 키가 노드보다 크면 오른쪽 서브트리에 삽입
    else if (key > node->key) {
        node->right = insert(node->right, key);
    }

    // 노드를 반환
    return node;
}

 

 C언어로 구현한 삽입 알고리즘의 예시. 재귀를 통해 키 값이 들어갈 수 있는 자리를 찾아 삽입한다.

 1. 현재 탐색중인 노드의 값보다 삽입할 값이 작으면 왼쪽으로 간다.

 2. 현재 탐색중인 노드의 값보다 삽입할 값이 크면 오른쪽으로 간다.

 3. 현재 탐색중인 노드가 비어있다면, 해당 위치에 삽입

 

 최악의 경우 트리에 존재하는 모든 노드가 자신보다 크거나 작을 수 있으므로 O(n)의 시간복잡도를 가진다. 하지만 평균적으로 O(log n)의 시간복잡도를 가진다.

 

 삭제

// 최소값을 찾는 함수
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;

    // 맨 왼쪽 끝까지 이동하여 가장 작은 값을 찾음
    while (current && current->left != NULL) {
        current = current->left;
    }

    return current;
}

// 노드를 삭제하는 함수
struct Node* deleteNode(struct Node* root, int key) {
    // 트리가 비어있으면 NULL을 반환
    if (root == NULL) {
        return root;
    }

    // 키가 루트보다 작으면 왼쪽 서브트리에서 삭제
    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    }
    // 키가 루트보다 크면 오른쪽 서브트리에서 삭제
    else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    }
    // 키가 루트와 같으면 이 노드를 삭제
    else {
        // 자식이 하나 또는 없는 경우
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // 자식이 두 개인 경우
        struct Node* temp = minValueNode(root->right);

        // 중위 순회에서 후계자의 값을 복사
        root->key = temp->key;

        // 후계자를 삭제
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

 

 삽입과 같이 재귀를 통해 삭제할 노드의 위치를 찾아낸다. 그 뒤 삭제의 문제는 중간에 있는 것을 삭제하는 경우인데, 그럴 때에는 삭제한 위치로 자식에 위치한 서브 트리를 한 칸 씩 위로 올리는 작업을 한다.

 

 탐색

// 이진 탐색 트리에서 키를 탐색하는 함수
struct Node* search(struct Node* root, int key) {
    // 루트가 NULL이거나 키가 루트의 키와 같으면 루트를 반환
    if (root == NULL || root->key == key) {
        return root;
    }

    // 키가 루트의 키보다 작으면 왼쪽 서브트리를 탐색
    if (key < root->key) {
        return search(root->left, key);
    }

    // 키가 루트의 키보다 크면 오른쪽 서브트리를 탐색
    return search(root->right, key);
}

 

 탐색도 삽입, 삭제와 마찬가지의 탐색 규칙에 따라 탐색을하여 찾게되면 반환을 한다.