레드블랙트리

////binary tree
////자료가 동적인 상태에서도 이진 탐색이 가능한 자료구조
////이진 탐색은 메모리 중심 대해서도 직접 접근이 가능, 미리 주어지고 정렬된 데이터 셋에만 적용이 가능하다.
////
////# 규칙
////현재 노드를 기준으로 왼쪽이 작은 값, 오른쪽이 큰 값인 규칙을 지닌다.
////
////# 용어
////leaf(잎) 노드 자식이 없는 노드
////root 최상단 노드
////root에서 잎노드 까지의 깊이: height
////
////완전포화이진트리
////: 잎 노드를 제외하고 완전하게 모든 노드가 자식이 있는 트리
////포화이진트리
////: 좌측 노드 까진 자식을 가지지만, 그 다음 부턴 자식이 없는 트리 
////불포화이진트리
////: 포화이진트리가 아닌 트리
////
////# 지원 연산
////1) insert
////2) search
////3) remove
//
#include <iostream>
using namespace std;

enum { RED, BLACK };
struct Tree
{
    Tree* pParent;
    Tree* pLeft;
    Tree* pRight;

    int data;
    int color;
};

Tree* root;
Tree* Nil;

struct Tree* createRBNode(int data)
{
    Tree* pNode = (Tree*)malloc(sizeof(Tree));
    pNode->pParent = nullptr;
    pNode->pLeft = nullptr;
    pNode->pRight = nullptr;
    pNode->data = data;

    return pNode;
}

void rotate_left(Tree* pRoot)
{
    if (pRoot == nullptr || pRoot->pRight == nullptr)
        return;

    Tree* pRootOrg = pRoot;
    Tree* pParent = nullptr;
    Tree* pLeftFromRootOrg = nullptr;
    Tree* pRightFromRootLeft = nullptr;

    if (pRoot->pLeft != Nil)
        pLeftFromRootOrg = pRoot->pLeft;

    if (pRoot->pRight->pLeft != Nil)
        pRightFromRootLeft = pRoot->pRight->pLeft;

    if (pRootOrg->pParent)
        pParent = pRootOrg->pParent;

    if (pParent) {
        pRoot->pParent = pParent;

        if (pParent->pLeft == pRoot) {
            pRoot = pRoot->pRight;
            pRoot->pParent = pParent;
            pParent->pLeft = pRoot;
        }
        else {
            pRoot = pRoot->pRight;
            pRoot->pParent = pParent;
            pRoot->pParent->pRight = pRoot;
        }
    }
    else {
        pRoot = pRoot->pRight;
        root = pRoot;
        root->pParent = nullptr;
    }

    pRoot->pLeft = pRootOrg;
    pRoot->pLeft->pParent = pRoot;

    if (pRightFromRootLeft) {
        pRoot->pLeft->pRight = pRightFromRootLeft;
        pRoot->pLeft->pRight->pParent = pRoot;
    }
    else {
        pRoot->pLeft->pRight = Nil;
    }
}

void rotate_right(Tree* pRoot)
{
    if (pRoot == nullptr || pRoot->pLeft == nullptr)
        return;

    Tree* pRootOrg = pRoot;
    Tree* pParent = nullptr;
    Tree* pRightFromRootOrg = nullptr;
    Tree* pRightFromRootLeft = nullptr;

    if (pRoot->pRight != Nil)
        pRightFromRootOrg = pRoot->pRight;

    if (pRoot->pLeft->pRight != Nil)
        pRightFromRootLeft = pRoot->pLeft->pRight;

    if (pRootOrg->pParent)
        pParent = pRootOrg->pParent;

    if (pParent) {
        pRoot->pParent = pParent;

        if (pParent->pLeft == pRoot) {
            pRoot = pRoot->pLeft;
            pRoot->pParent = pParent;
            pParent->pLeft = pRoot;

        }
        else {
            pRoot = pRoot->pLeft;
            pRoot->pParent = pParent;
            pRoot->pParent->pRight = pRoot;
        }
    }
    else {
        pRoot = pRoot->pLeft;
        root = pRoot;
        root->pParent = nullptr;
    }

    pRoot->pRight = pRootOrg;
    pRoot->pRight->pParent = pRoot;

    if (pRightFromRootLeft) {
        pRoot->pRight->pLeft = pRightFromRootLeft;
        pRoot->pRight->pLeft->pParent = pRoot;
    }
    else {
        pRoot->pRight->pLeft = Nil;
    }
}

void preorder(Tree* ptree)
{
    char c = ptree->color == RED ? 'R' : 'B';
    printf("[%d c: %c]", ptree->data, c);

    if (ptree->pLeft != Nil)
        preorder(ptree->pLeft);

    if (ptree->pRight != Nil)
        preorder(ptree->pRight);
}

void inorder(Tree* ptree)
{
    if (ptree->pLeft != Nil)
        inorder(ptree->pLeft);

    printf("%d ", ptree->data);

    if (ptree->pRight != Nil)
        inorder(ptree->pRight);
}

void postorder(Tree* ptree)
{
    if (ptree->pLeft != Nil)
        postorder(ptree->pLeft);

    if (ptree->pRight != Nil)
        postorder(ptree->pRight);

    printf("%d ", ptree->data);
}

void insert_BT(Tree* pTree, Tree* pNewNode)
{
    if (pTree->data > pNewNode->data)
    {
        if (pTree->pLeft != Nil)
            insert_BT(pTree->pLeft, pNewNode);
        else {
            pTree->pLeft = pNewNode;
            pNewNode->pParent = pTree;
        }
    }
    else if (pTree->data < pNewNode->data)
    {
        if (pTree->pRight != Nil)
            insert_BT(pTree->pRight, pNewNode);
        else {
            pTree->pRight = pNewNode;
            pNewNode->pParent = pTree;
        }
    }
}

void rebuild_RB_for_Insert(Tree* pTree)
{
    Tree* pCurTree = pTree;

    if (pCurTree->pParent == nullptr)
        return;
    if (pCurTree->pParent->pParent == nullptr)
        return;

    while (pCurTree != root && pCurTree->pParent->color == RED)
    {
        Tree* pUncle = nullptr;
        if (pCurTree->pParent->pParent->pLeft == pCurTree->pParent) {
            pUncle = pCurTree->pParent->pParent->pRight;

            int uncleColor = -1;

            if (pUncle != Nil) {
                // 1) 삼촌이 빨간색인 경우
                if (pUncle->color == RED) {
                    pCurTree->pParent->color = BLACK;
                    pUncle->color = BLACK;

                    if (pCurTree->pParent->pParent != root) {
                        pCurTree->pParent->pParent->color = RED;
                        pCurTree = pCurTree->pParent->pParent;
                    }
                }

                uncleColor = pUncle->color;
                continue;
            }

            // 2) 삼촌이 검은색이고
            if (pUncle == Nil || uncleColor == BLACK) {
                // 새로 입력된 노드가 부모의 왼쪽에 위치하는 경우
                if (pCurTree->pParent->pLeft == pCurTree) {
                    pCurTree->pParent->color = BLACK;
                    pCurTree->pParent->pParent->color = RED;
                    rotate_right(pCurTree->pParent->pParent);
                }
                // 새로 입력된 노드가 부모의 오른쪽에 위치하는 경우
                else {
                    pCurTree = pCurTree->pParent;
                    rotate_left(pCurTree);
                }
            }
        }
        else {
            pUncle = pCurTree->pParent->pParent->pLeft;

            Tree* pUncle = nullptr;
            if (pCurTree->pParent->pParent->pRight == pCurTree->pParent) {
                pUncle = pCurTree->pParent->pParent->pLeft;

                int uncleColor = -1;

                if (pUncle != Nil) {
                    // 1) 삼촌이 빨간색인 경우
                    if (pUncle->color == RED) {
                        pCurTree->pParent->color = BLACK;
                        pUncle->color = BLACK;

                        if (pCurTree->pParent->pParent != root) {
                            pCurTree->pParent->pParent->color = RED;
                            pCurTree = pCurTree->pParent->pParent;
                        }
                    }

                    uncleColor = pUncle->color;
                    continue;
                }

                // 2) 삼촌이 검은색이고
                if (pUncle == Nil || uncleColor == BLACK) {
                    // 새로 입력된 노드가 부모의 왼쪽에 위치하는 경우
                    if (pCurTree->pParent->pRight == pCurTree) {
                        pCurTree->pParent->color = BLACK;
                        pCurTree->pParent->pParent->color = RED;
                        rotate_left(pCurTree->pParent->pParent);
                    }
                    // 새로 입력된 노드가 부모의 오른쪽에 위치하는 경우
                    else {
                        pCurTree = pCurTree->pParent;
                        rotate_right(pCurTree);
                    }
                }
            }
        }
    }
}

void insert_RB(Tree* pTree, Tree* pNewNode)
{
    insert_BT(pTree, pNewNode);

    pNewNode->color = RED;
    pNewNode->pLeft = Nil;
    pNewNode->pRight = Nil;

    rebuild_RB_for_Insert(pNewNode);
}

Tree* search_BT(Tree* pTree, int data)
{
    if (pTree == Nil)
        return NULL;

    if (pTree->data > data)
    {
        if (pTree->pLeft)
            return search_BT(pTree->pLeft, data);
    }
    else if (pTree->data < data)
    {
        if (pTree->pRight)
            return search_BT(pTree->pRight, data);
    }
    else {
        return pTree;
    }

    return NULL;
}

Tree* findMinNode(Tree* pParent, Tree* pTree)
{
    Tree* pCur = pTree;

    while (pCur->pLeft != Nil) {
        pParent = pCur;
        pCur = pCur->pLeft;
    }

    return pCur;
}

void rebuild_RB_for_Remove(Tree* pSuccessor)
{
    Tree* pCurNode = pSuccessor;
    Tree* sibling = nullptr;

    while (pCurNode != root && pCurNode->color == BLACK) {
        if (pCurNode->pParent->pLeft == pCurNode) {
            sibling = pCurNode->pParent->pRight;

            // 1) 형제 노드가 빨간색인 경우 -> 형제 노드가 검은색이 나올 때 까지 시행된다.
            if (sibling->color == RED) {
                sibling->color = BLACK;
                sibling->pParent->color = RED;
                rotate_left(sibling->pParent);
                continue;
            }

            // 2) 형제 노드가 검은색인 경우
            else {
                // 2-1) 두 자식이 다 검은색인 경우
                if (sibling->pLeft->color == BLACK && sibling->pRight->color == BLACK) {
                    sibling->color = RED;
                    pCurNode = pCurNode->pParent;
                }

                else {
                    // 2-2) 오른쪽 자식이 빨간색인 경우
                    if (sibling->pLeft->color == RED) {
                        // 2-3) 형제 노드의 왼쪽 자식이 빨간색이고, 오른쪽 자식이 검은색인 경우
                        // 형제 노드를 빨간색으로 칠한다.
                        sibling->color = RED;

                        // 형재 노드의 왼쪽 자식을 검은색으로 칠한다.
                        sibling->pLeft->color = BLACK;
                        // 오른쪽으로 회전한다.
                        rotate_right(sibling);
                    }
                    else if (sibling->pRight->color == RED) {
                        // 2-3) 왼쪽 자식이 빨간색인 경우
                        // 이중 흑색노드의 부모의 색을 형제에게 전달한다.
                        sibling->color = pCurNode->pParent->color;

                        // 형제의 오른쪽 자식, 이중 흑색 노드의 부모의 색을 검은색으로 칠한다.
                        sibling->pRight->color = BLACK;
                        sibling->pParent->color = BLACK;

                        // 좌회전을 한다.
                        rotate_left(sibling->pParent);

                        // 이중 흑색 노드를 루트 노드로 변경한다.
                        pCurNode = root;
                    }
                }
            }
        }
        else {
            sibling = pSuccessor->pParent->pLeft;

            if (sibling->color == RED) {
                sibling->color = BLACK;
                sibling->pParent->color = RED;
                rotate_right(sibling->pParent);
                continue;
            }

            // 2) 형제 노드가 검은색인 경우
            else {
                // 2-1) 두 자식이 다 검은색인 경우
                if (sibling->pRight->color == BLACK && sibling->pLeft->color == BLACK) {
                    sibling->color = RED;
                    pCurNode = pCurNode->pParent;
                }

                // 2-2) 형제 노드의 왼쪽 자식이 검은색이고, 오른쪽 자식이 빨간색인 경우
                else {
                    if (sibling->pRight->color == RED) {
                        // 형제 노드를 빨간색으로 칠한다.
                        sibling->color = RED;

                        // 형재 노드의 왼쪽 자식을 검은색으로 칠한다.
                        sibling->pRight->color = BLACK;

                        // 오른쪽으로 회전한다.
                        rotate_left(sibling);
                    }
                    else if (sibling->pLeft->color == RED) {
                        // 이중 흑색노드의 부모의 색을 형제에게 전달한다.
                        sibling->color = pCurNode->pParent->color;

                        // 형제의 오른쪽 자식, 이중 흑색 노드의 부모의 색을 검은색으로 칠한다.
                        sibling->pLeft->color = BLACK;
                        sibling->pParent->color = BLACK;

                        // 좌회전을 한다.
                        rotate_right(sibling->pParent);

                        // 이중 흑색 노드를 루트 노드로 변경한다.
                        pCurNode = root;
                    }
                }
            }
        }
    }
    pCurNode->color = BLACK;
}

Tree* remove_BT(Tree* pTree, Tree* pParent, int data)
{
    Tree* pRemoved = nullptr;
    if (pTree != Nil) {
        if (pTree->data > data)
        {
            if (pTree->pLeft)
                return remove_BT(pTree->pLeft, pTree, data);
        }
        else if (pTree->data < data)
        {
            if (pTree->pRight)
                return remove_BT(pTree->pRight, pTree, data);
        }
        else {
            if (pTree->pLeft == Nil && pTree->pRight == Nil) {
                // 현재 노드를 삭제하고 부모가 갖는 left or right에 해당하는 곳엔 nullptr 추가
                pRemoved = pTree;

                if (root == pTree) {
                    root = nullptr;
                }
                else {
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = Nil;
                    }
                    else {
                        pParent->pRight = Nil;
                    }
                }
            }
            else if (pTree->pLeft == Nil || pTree->pRight == Nil) {
                // 현재 노드를 삭제하고 자식을 부모의 left or right에 해당하는 곳에 추가.
                Tree* pNode = nullptr;
                if (pTree->pLeft != Nil) {
                    pNode = pTree->pLeft;
                }
                else {
                    pNode = pTree->pRight;
                }

                pRemoved = pTree;

                if (root == pTree) {
                    root = pNode;
                    root->pParent = nullptr;
                }
                else {

                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pNode;
                    }
                    else {
                        pParent->pRight = pNode;
                    }
                    pNode->pParent = pParent;
                }
            }
            else if (pTree->pLeft != Nil && pTree->pRight != Nil) {
                // 1) 오른쪽 트리의 최소 자식을 찾는다.
                Tree* pMinNode = findMinNode(pTree, pTree->pRight);
                pRemoved = pTree;

                if (root == pTree) {
                    root = pMinNode;
                    root->pParent = nullptr;
                }
                else {
                    // 2) 부모에 단다.
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pMinNode;
                    }
                    else {
                        pParent->pRight = pMinNode;
                    }
                    pMinNode->pParent = pParent;
                }

                pMinNode->pLeft = pTree->pLeft;
                pMinNode->pRight = pTree->pRight;
            }

            return pRemoved;
        }
    }

    return pRemoved;
}

Tree* remove_RB(Tree* pRoot, int data)
{
    Tree* pTarget = search_BT(pRoot, data);
    Tree* pSuccessor = nullptr;
    Tree* pRemoved = nullptr;

    if (pTarget == nullptr) {
        return nullptr;
    }

    if (pTarget->pLeft == Nil || pTarget->pRight == Nil) {
        pRemoved = pTarget;
    }

    if (pTarget->pLeft != Nil && pTarget->pRight != Nil) {
        pRemoved = findMinNode(pTarget, pTarget->pRight);
        pTarget->data = pRemoved->data;
    }

    if (pRemoved->pLeft != Nil) {
        pSuccessor = pRemoved->pLeft;
    }
    else {
        pSuccessor = pRemoved->pRight;
    }

    pSuccessor->pParent = pRemoved->pParent;

    if (pRemoved->pParent == nullptr) {
        root = pSuccessor;
    }
    else {
        if (pRemoved->pParent->pLeft == pRemoved) {
            pRemoved->pParent->pLeft = pSuccessor;
        }
        else {
            pRemoved->pParent->pRight = pSuccessor;
        }
    }

    if (pRemoved->color == BLACK) {
        rebuild_RB_for_Remove(pSuccessor);
    }

    return pRemoved;
}

void remove_node(Tree* node)
{
    if (node)
        free(node);
}

void destroy(Tree* pTree)
{
    if (pTree->pLeft != Nil)
        destroy(pTree->pLeft);

    if (pTree->pRight != Nil)
        destroy(pTree->pRight);

    free(pTree);
}

void printParent(Tree* pTree)
{
    Tree* pCur = pTree;
    Tree* pLocalParent = pTree;

    while (pCur) {
        printf("%d ", pCur->data);
        pCur = pCur->pParent;
    }
    printf("\n\n");
}

void printLeftChild(Tree* pTree)
{
    Tree* pCur = pTree;
    Tree* pLocalParent = pTree;

    while (pCur) {
        printf("%d ", pCur->data);
        pCur = pCur->pLeft;
    }
}

int main()
{
    // 1) define nil node
    Nil = createRBNode(0);
    Nil->color = BLACK;

    root = createRBNode(20);
    root->color = BLACK;
    root->pLeft = Nil;
    root->pRight = Nil;

    insert_RB(root, createRBNode(15));
    insert_RB(root, createRBNode(3));
    insert_RB(root, createRBNode(12));
    insert_RB(root, createRBNode(5));
    insert_RB(root, createRBNode(11));
    insert_RB(root, createRBNode(6));
    insert_RB(root, createRBNode(40));
    insert_RB(root, createRBNode(25));
    insert_RB(root, createRBNode(18));

    Tree* pRemoveTarget = remove_RB(root, 5);
    free(pRemoveTarget);

    pRemoveTarget = remove_RB(root, 6);
    free(pRemoveTarget);

    pRemoveTarget = remove_RB(root, 12);
    free(pRemoveTarget);

    pRemoveTarget = remove_RB(root, 25);
    free(pRemoveTarget);

    pRemoveTarget = remove_RB(root, 3);
    free(pRemoveTarget);
    //
    pRemoveTarget = remove_RB(root, 11);
    free(pRemoveTarget);
    //
    pRemoveTarget = remove_RB(root, 15);
    free(pRemoveTarget);
    //
    pRemoveTarget = remove_RB(root, 18);
    free(pRemoveTarget);
    //
    pRemoveTarget = remove_RB(root, 20);
    free(pRemoveTarget);
    //
    pRemoveTarget = remove_RB(root, 40);
    free(pRemoveTarget);

    if (root) {
        preorder(root);
        //inorder(root);
        //postorder(root);
    }
    else {
        printf("no data in tree\n");
    }

    if (root)
        destroy(root);
    free(Nil);

    return 0;
}

다음은 레드 블랙트리에 대한 코드이다. 코드 설명과 그림 추가 예정 // 삭제 코드 작성필요