[c++] 레드-블랙 트리의 삭제(Red-Black Tree Deletion)

12 Dec 2023

레드-블랙 트리에서 노드를 삭제하는 과정은 까다로운데, 레드-블랙 트리의 속성을 만족시키기 위해 균형을 맞춰야 합니다. 레드-블랙 트리의 삭제 알고리즘은 여러 경우의 수를 고려해야 하며, 이는 다른 이진 검색 트리들보다 더 복잡합니다.

레드-블랙 트리의 삭제 알고리즘

레드-블랙 트리에서 노드를 삭제할 때는 일반적으로 다음과 같은 단계를 따릅니다.

이진 검색 트리의 노드 삭제처럼 삭제 대상 노드를 식별하고, 해당 노드를 삭제합니다.
삭제된 노드의 자식 노드의 수에 따라 다른 조치를 취합니다.
삭제된 노드의 자리를 대체할 적절한 노드를 찾아야 합니다.
삭제된 노드의 대체 노드를 조율하여 레드-블랙 트리의 속성을 유지합니다.

C++ 레드-블랙 트리 삭제의 예시

다음은 C++로 구현된 레드-블랙 트리의 삭제 알고리즘의 간단한 예제입니다.

void RBTree::deleteNode(Node* v) {
    // 삭제될 노드의 조상
    Node* u = getBSTReplace(v);

    // v를 u로 대체하여 삭제
    bool uvBlack = ((u == NULL || u->color == BLACK) && (v->color == BLACK));
    Node* parent = v->parent;
    if (u == NULL) {
        // u가 NULL인 경우
        if (v == root) {
            // 삭제될 노드가 루트 노드인 경우
            root = NULL;
        } else {
            if (uvBlack) {
                // 삭제된 노드와 대체된 노드가 동시에 블랙인 경우
                fixDoubleBlack(v);
            } else {
                if (v->sibling() != NULL) {
                    // 삭제된 노드에 형제 노드가 있는 경우
                    v->sibling()->color = RED;
                }
            }

            // 삭제될 노드 삭제
            if (v->isOnLeft()) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        }
        delete v;
        return;
    }

    if (v->left == NULL || v->right == NULL) {
        // 삭제될 노드의 자식 노드가 하나 뿐인 경우
        if (v == root) {
            // 삭제될 노드가 루트 노드인 경우
            v->data = u->data;
            v->left = v->right = NULL;
            delete u;
        } else {
            if (v->isOnLeft()) {
                parent->left = u;
            } else {
                parent->right = u;
            }
            delete v;
            u->parent = parent;
            if (uvBlack) {
                // 삭제된 노드와 대체된 노드가 동시에 블랙인 경우
                fixDoubleBlack(u);
            } else {
                // 대체된 노드를 블랙으로 만듦
                u->color = BLACK;
            }
        }
        return;
    }

    // 삭제될 노드의 자식 노드가 둘 다 있는 경우
    swapValues(u, v);
    deleteNode(u);
}

이 코드는 레드-블랙 트리에서 노드를 삭제하는 알고리즘을 구현한 것입니다.

마무리

레드-블랙 트리에서 노드를 삭제하는 과정은 다른 이진 검색 트리들보다 더 복잡합니다. 따라서 정확한 알고리즘을 통해 레드-블랙 트리의 속성을 유지하면서 노드를 삭제해야 합니다. C++을 사용하여 레드-블랙 트리의 삭제 알고리즘을 구현하는 방법에 대해 알아보았습니다.

참고 문헌: GeeksforGeeks - Red Black Tree (Delete)