자료구조 - 이진 탐색 트리

[이진 탐색 트리(Binary Search Tree)]

이진 트리 기반이 탐색을 귀한 자료 구조입니다.

 

이진 탐색 트리의 정의

● 모든 원소의 키는 유일한 키를 가진다.
● 왼쪽 서브 트리 키들은 루트 키보다 작다.
● 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
● 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

 

 

 

 

순환적인 탐색연산

순환적인 탐색 연산은 주어진 키를 가진 노드를 찾는 작업입니다. 이를 재귀적으로 수행할 수 있습니다.

재귀적인 방법은 현재 노드와 키를 비교하고, 작으면 왼쪽 서브트리에서, 크면 오른쪽 서브트리에서 재귀적으로 탐색합니다.

 

TreeNode* searchRecursive(TreeNode* root, int key) 
{
    // 루트가 없거나 루트가 키와 같으면 루트를 반환
    if (root == nullptr || root->key == key)
    {
        return root;
    }
    
    // 키가 루트의 키보다 작으면 왼쪽 서브트리에서 재귀적으로 탐색
    if (key < root->key)
    {
        return searchRecursive(root->left, key);
    }
    // 키가 루트의 키보다 크면 오른쪽 서브트리에서 재귀적으로 탐색
    else
    {
        return searchRecursive(root->right, key);
    }
}

 

 

 

 

 

반복적인 탐색연산

반복적인 탐색 연산은 순환적인 연산과 유사하지만, 반복문을 사용하여 구현합니다.

현재 노드와 키를 비교하여 작으면 왼쪽으로 이동하고, 크면 오른쪽으로 이동합니다.

이를 반복하여 키를 찾거나 노드가 없을 때까지 반복합니다.

TreeNode* searchIterative(TreeNode* root, int key) 
{
    while (root != nullptr && root->key != key) 
    {
        if (key < root->key) 
        {
            root = root->left;
        } 
        
        else 
        {
            root = root->right;
        }
    }
    return root;
}

 

 

 

[삽입 연산과 삭제 연산]

 

삽입 연산

삽입 연산은 주어진 키를 가진 노드를 삽입하는 작업입니다.

먼저 순환적인 탐색이나 반복적인 탐색을 사용하여 삽입 위치를 찾은 후에 새로운 노드를 해당 위치에 삽입합니다.

void insert(TreeNode*& root, int key)
{
    if (root == nullptr) 
    {
        root = new TreeNode(key);
        return;
    }

    if (key < root->key)
    {
        insert(root->left, key);
    } 
    else 
    {
        insert(root->right, key);
    }
}

 

 

 

삭제 연산

삭제 연산은 주어진 키를 가진 노드를 삭제하는 작업입니다.

삭제할 노드가 없는 경우를 처리해야 하며, 삭제할 노드가 단말 노드인 경우, 자식이 하나인 경우, 자식이 둘인 경우를 고려해야 합니다.

 

 

1. 삭제하려는 노드가 자식이 없는 경우

이 경우에는 단말노드 아래에 노드가 없으므로 단말노드만 지우면 됩니다.

단말노드를 지운다는 것은 단말도느의 부모노드의 링크필드를 NULL로 만들어주면 됩니다.

 

2. 삭제하려는 노드가 자식이 하나인 경우

삭제하려는 노드의 왼쪽이나 오른쪽에 자식이 있지만 신경쓰지 않아도 됩니다.

삭제하려는 노드를 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여주면 됩니다.

3. 삭제하려는 노드가 자식이 둘인 경우

자식이 둘인 경우에는 삭제하려는 노드의 왼쪽 서브 트리에서 제일 큰 값이나 오른쪽 서브 트리에서 제일 작은 값을 삭제하려는 노드의 위치에 옮겨주면 됩니다.

 

 

이진 탐색트리의 삭제 연산

// 주어진 노드 아래에서 가장 작은 값을 가진 노드를 찾는 함수
TreeNode* minValueNode(TreeNode* node)
{
    TreeNode* current = node;
    
    // 왼쪽 자식이 없는 노드까지 이동
    while (current->left != nullptr) 
    {
        current = current->left;
    }
    return current;
}

// 이진 탐색 트리에서 노드를 삭제하는 함수
TreeNode* deleteNode(TreeNode* root, int key)
{
    // 빈 트리인 경우
    if (root == nullptr) 
    {
        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 == nullptr && root->right == nullptr) 
        {
            delete root;
            root = nullptr;
        }
        // 자식이 하나인 경우
        else if (root->left == nullptr) 
        {
            TreeNode* temp = root;
            root = root->right;
            delete temp;
        }
        else if (root->right == nullptr) 
        {
            TreeNode* temp = root;
            root = root->left;
            delete temp;
        }
        // 자식이 둘인 경우
        else 
        {
            // 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾아 삭제할 노드로 대체
            TreeNode* temp = minValueNode(root->right);
            root->key = temp->key;
            // 오른쪽 서브트리에서 대체한 노드 삭제
            root->right = deleteNode(root->right, temp->key);
        }
    }
    return root;
}

 

minValueNode 함수는 주어진 노드 아래에서 가장 작은 값을 가진 노드를 찾습니다.

그 후, 삭제할 노드를 찾고 해당 노드를 삭제하거나 대체합니다.

이렇게 함으로써 이진 탐색 트리의 불변 조건을 유지하면서 노드를 삭제할 수 있습니다.