이진 검색 트리(BST)

이진 검색 트리

이진 검색 트리는 다음과 같은 특성을 가진다.

• 부모 노드의 값이 왼쪽 자식 노드의 값보다 크다.
• 부모 노드의 값이 오른쪽 자신 노드의 값보다 작다.

이러한 특성 덕분에 이상적인 상황에서 매 검색 단계마다 검색 범위가 절반으로 줄어들며 검색 동작의 시간 복잡도는 O(logN)가 된다.

이진 검색 트리에서의 원소 검색

1. 현재 노드(시작은 루트 노드)의 값을 찾는 값과 비교
2. 찾는 값이 현재 노드의 값보다 작다면 왼쪽 자식 노드로 이동
3. 찾는 값이 현재 노드의 값보다 크다면 오른쪽 자식 노드로 이동
4. 값을 찾을 때까지 1~3번의 작업 반복

    node* find_impl(node* current, int value)
    {
        if (!current)
        {
            std::cout << std::endl;
            return NULL;
        }


        if (current->data == value)
        {
            std::cout << value << "을(를) 찾았습니다." << std::endl;
            return current;
        }


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


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

이진 검색 트리에서의 새 원소 삽입

1. 현재 노드(시작은 루트 노드)의 값을 삽입하려는 값과 비교
2. 현재 노드의 값이 삽입하려는 값보다 작다면 왼쪽 자식 노드가 존재하는지 검사, 존재 하지 않는다면 왼쪽 자식 노드로 값 삽입
3. 현재 노드의 값이 삽입하려는 값보다 크다면 오른쪽 자식 노드가 존재하는지 검사, 존재 하지 않는다면 오른쪽 자식 노드로 값 삽입
4. 2, 3번의 경우, 자식 노드가 존재 한다면 그 자식 노드에서 삽입 동작 계속

    void insert_impl(node* current, int value)
    {
        if (value < current->data)
        {
            if (!current->left)
                current->left = new node{ value,NULL, NULL };
            else
                insert_impl(current->left, value);
        }
        else
        {
            if (!current->right)
                current->right = new node{ value, NULL, NULL };
            else
                insert_impl(current->right, value);
        }
    }

이진 검색 트리에서의 원소 삭제

1. 삭제하려는 원소 검색
2. 세가지 경우가 있음

• 자식 노드가 없는 경우: 해당 노드 삭제
• 자식 노드가 하나만 있는 경우: 노드 삭제 후, 부모 노드가 해당 자식 노드를 가리키도록 조정
• 자식 노드가 두 개 있는 경우: 노드 삭제 후, 현재 노드를 후속 노드로 대체, 후속 노드: 현재 원소보다 큰 원소들 중 가장 작은 원소, 현재 노드의 오른쪽으로 이동 후 가장 왼쪽 노드를 찾으면 됨
  

    node* delete_impl(node* start, int value)
    {
        if (!start)
            return NULL;


        if (value < start->data)
            start->left = delete_impl(start->left, value);
        else if (value > start->data)
            start->right = delete_impl(start->right, value);
        else // 삭제하려는 노드를 찾을 경우
        {
            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);
        }