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

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)

• 널리 사용되는 형태의 이진 트리(Binary Tree)
• BST의 속성
  • 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐.
    • 부모 노드의 값 ≥ 왼쪽 자식 노드의 값
    • 부모 노드의 값 ≤ 오른쪽 자식 노드의 값
• 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨.
  • 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦.
• BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우
  • 트리의 높이 : log₂N
    • N : 원소의 개수
  • BST의 검색 및 삽입 동작의 시간 복잡도 : O(logN)
  • 이러한 형태의 이진 트리를 완전 이진 트리(Complete Binary Tree) 라고 함.

 

탐색 연산

• 이진 검색 트리에서 현재 노드보다 왼쪽 노드는 값이 작고, 오른쪽 노드는 값이 크다 는 점을 기억해야 함.
• BST에서 원소를 검색할 때는, 트리의 모든 원소를 방문하지 않아도 됨.
  • 현재 노드가 찾고자 하는 노드가 아닐 때마다 검색 범위가 반으로 줄어듦.

 

삽입 연산

• 새로운 원소를 추가하려면 원소가 삽입될 위치의 부모 노드 를 찾아야 함.
  • 원소 검색과 비슷한 접근 방식을 사용하면 됨.
    • 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하면서 원소가 삽입될 위치로 이동해야 함.

 

삭제 연산

• BST에서 원소를 삭제하는 작업은 단순히 노드를 삭제하는 것으로 끝나는 것이 아님.
  • 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 다른 적절한 노드로 삭제된 노드를 대체해야 하기 때문에 삽입보다 좀 더 복잡함.
• 노드를 삭제할 때, 다음의 3가지 경우를 따져봐야 함.
  • 자식 노드가 없는 경우
    • 단순하게 해당 노드 삭제
  • 자식 노드가 1개만 있는 경우
    • 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정
  • 자식 노드가 2개 있는 경우
    • 노드 삭제 후, 현재 노드를 후속 노드(Successor) 로 대체
      • 후속 노드(Successor)
        • 현재 노드 다음으로 큰 숫자를 가진 노드
        • 현재 원소보다 큰 원소들 중에서 가장 작은 원소
        • 현재 노드의 오른쪽 서브 트리로 이동한 후, 여기서 가장 작은 값의 노드 를 찾으면 됨.
          • 가장 작은 노드를 찾으려면, 서브 트리에서 가장 왼쪽에 위치한 노드 로 이동하면 됨.

 

구현

 

#include <iostream>

struct node {
    int data;
    node* left;
    node* right;
};

struct bst {
    node* root = nullptr;

    node* find(int value) {
        return find_impl(root, value);
    }

private:
    node* find_impl(node* current, int value) {
        // 노드가 존재하지 않을 경우
        if (!current) {
            std::cout << std::endl;
            return NULL;
        }

        // value 값이 현재 노드에 있는 경우
        if (current->data == value) {
            std::cout << value << "을(를) 찾았습니다. " << std::endl;
            return current;
        }

        // value 값이 현재 노드 왼쪽에 있는 경우
        if (value < current->data) {
            std::cout << current->data << "에서 왼쪽으로 이동: ";
            return find_impl(current->left, value);
        }

        // value 값이 현재 노드 오른쪽에 있는 경우
        std::cout << current->data <<"에서 오른쪽으로 이동: ";
        return find_impl(current->right, value);
    }

public:
    void insert(int value) {
        if (!root) {                                // 1. 루트 노드가 없을 경우
            root = new node {value, NULL, NULL};
        }
        else {                                      // 2. 루트 노드가 있을 경우
            insert_impl(root, value);
        }
    }

private:
    void insert_impl(node* current, int value) {
        if (value < current->data) {                                //// 1. 왼쪽 서브 트리에 원소를 삽입해야 할 경우
            if (!current->left) {                                   // (1) 왼쪽 자식 노드가 존재하지 않을 경우
                current->left = new node {value, NULL, NULL};
            }
            else {                                                  // (2) 왼쪽 자식 노드가 존재할 경우
                insert_impl(current->left, value);
            }
        }
        else {                                                      //// 2. 오른쪽 서브 트리에 원소를 삽입해야 할 경우
            if (!current->right) {                                  // (1) 오른쪽 자식 노드가 존재하지 않을 경우
                current->right = new node {value, NULL, NULL};
            }
            else {                                                  // (2) 오른쪽 자식 노드가 존재할 경우
                insert_impl(current->right, value);
            }
        }
    }

public:
    void inorder() {
        inorder_impl(root);
    }

private:
    void inorder_impl(node* start) {
        if (!start) {
            return;
        }
        inorder_impl(start->left);                  // 왼쪽 서브 트리 방문
        std::cout << start->data << " ";            // 현재 노드 출력
        inorder_impl(start->right);                 // 오른쪽 서브 트리 방문
    }

public:
    node* successor(node* start) {
        auto current = start->right;                // 오른쪽 서브 트리로 이동
        while (current && current->left) {          // 왼쪽 하위 노드가 존재할 때까지 계속 반복
            current = current->left;                // 왼쪽의 하위 노드를 후속 노드로 설정
        }
        return current;
    }

	void deleteValue(int value) {
    	root = delete_impl(root, value);
	}

private:
    node* delete_impl(node* start, int value) {
        // 노드가 없을 경우
        if (!start) {
            return NULL;
        }

        if (value < start->data) {                              // (1) 삭제하고자 하는 원소가 현재 노드의 왼쪽 서브 트리에 있을 경우
            start->left = delete_impl(start->left, value);
        }
        else if (value > start->data) {                         // (2) 삭제하고자 하는 원소가 현재 노드의 오른쪽 서브 트리에 있을 경우
            start->right = delete_impl(start->right, value);
        }
        else {                                                  // (3) 삭제하고자 하는 원소가 현재 노드에 있을 경우
            // 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
            if (!start->left) {
                auto tmp = start->right;
                delete start;
                return tmp;
            }

            // 오른쪽 자식 노드만 없는 경우
            if (!start->right) {
                auto tmp = start->left;
                delete start;
                return tmp;
            }

            // 자식 노드가 둘 다 있는 경우
            auto succNode = successor(start);
            start->data = succNode->data;

            // 오른쪽 서브 트리에서 후속(successor)을 찾아 삭제
            start->right = delete_impl(start->right, succNode->data);
        }

        return start;
    }
};

int main() {
    bst tree;
    tree.insert(12);
    tree.insert(10);
    tree.insert(20);
    tree.insert(8);
    tree.insert(11);
    tree.insert(15);
    tree.insert(28);
    tree.insert(4);
    tree.insert(2);

    std::cout << "중위 순회: ";
    tree.inorder();                     // BST의 모든 원소를 오름차순으로 출력
    std::cout << std::endl;

    tree.deleteValue(12);
    std::cout << "12를 삭제한 후 중위 순회: ";
    tree.inorder();                     // BST의 모든 원소를 오름차순으로 출력
    std::cout << std::endl;

    if (tree.find(12)) {
        std::cout << "원소 12는 트리에 있습니다." << std::endl;
    }
    else {
        std::cout << "원소 12는 트리에 없습니다." << std::endl;
    }

    return 0;
}

 

결과

중위 순회: 2 4 8 10 11 12 15 20 28 
12를 삭제한 후 중위 순회: 2 4 8 10 11 15 20 28 
15에서 왼쪽으로 이동: 10에서 오른쪽으로 이동: 11에서 오른쪽으로 이동: 
원소 12는 트리에 없습니다.