红黑树C语言实现

1. 红黑树理解和推导详见

2. C语言代码

由于加了不少代码用于打印树和增改中的Log,所以整体会略长。

#include <stdio.h>
#include <stdlib.h>

typedef enum Side{//用于标示当前的镜像模式,避免重复写镜像的代码
    kLeft = 0,
    kRight = 1,
}Side;

typedef enum Color{
    kRed = 0,
    kBlack = 1,
}Color;

typedef struct TreeNode{
    int key;
    Color color;
    struct TreeNode *pFather;
    struct TreeNode *pChilds[2];
}TreeNode;

TreeNode* GetANewTreeNode(const int kKey,const Color kColor){
    TreeNode *pNewNode = calloc(1,sizeof(TreeNode));
    pNewNode->key = kKey;
    pNewNode->color = kColor;
    pNewNode->pFather = NULL;
    pNewNode->pChilds[kLeft] = NULL;
    pNewNode->pChilds[kRight] = NULL;
    return pNewNode;
}

int FreeTreeNode(TreeNode **kppNode){
    free((TreeNode*) *kppNode);
    *kppNode = NULL;
}

TreeNode* SearchTreeByKey(const int kKey,const TreeNode *kpTreeRoot){
    TreeNode *pSearchingNode = (TreeNode*)kpTreeRoot;
    while(pSearchingNode != NULL){
        if(pSearchingNode->key == kKey){//Have found it!
            return pSearchingNode;
        }
        if(pSearchingNode->key > kKey){
            pSearchingNode = pSearchingNode->pChilds[kLeft];
            continue;
        }else{
            pSearchingNode = pSearchingNode->pChilds[kRight];
            continue;
        }
    }
    return NULL;
}

int Max(const int a,const int b){
    if(a >= b){
        return a;
    }else{
        return b;
    }
}

int Power(const int a,const int p){
    int result = 1;
    for(int i = 0;i < p;i++){
        result *= a;
    }
    return result;
}

int TreeDepth(const TreeNode* root){
    if(root == NULL){
        return 0;
    }
    return Max(TreeDepth(root->pChilds[kLeft]),TreeDepth(root->pChilds[kRight])) + 1;
}

void PrintTree(const TreeNode* root){
    const int queueSize = 10000;
    TreeNode* pNodesQueue[queueSize];
    int nodesRow[queueSize];
    int queueStart = 0;
    int queueEnd = 0;
    
    TreeNode* pReadingNode = (TreeNode*)root;
    int readingNodeRow = 1;
    
    int lastRow = 0;
    int lastCol = 0;
    if(pReadingNode != NULL){
        pNodesQueue[queueEnd] = pReadingNode;
        nodesRow[queueEnd] = 1;
        queueEnd = (queueEnd + 1) % queueSize;
    }
    
    int maxDepth = TreeDepth(root);
    while(queueStart != queueEnd){
        pReadingNode = pNodesQueue[queueStart];
        readingNodeRow = nodesRow[queueStart];
        queueStart = (queueStart + 1) % queueSize;
        
        if(lastRow != readingNodeRow)
        {
            lastCol = 0;
            if(lastRow != 0){
                printf("\n");
            }
            lastRow = readingNodeRow;
            if(readingNodeRow != maxDepth){
                for(int i = 0;i < Power(2,maxDepth - readingNodeRow - 1) * 3 - 2;i++)
                    printf("   ");
            }
        }else{
            if(readingNodeRow != maxDepth){
                for(int i = 0;i < Power(2,maxDepth - readingNodeRow) * 3 - 1;i++)
                printf("  ");
            }else{
                for(int i = 0;i < 2;i++)
                printf("  ");
            }
        }
        
        
        lastCol++;
        
        if(pReadingNode != NULL){
            if(pReadingNode->color == kRed){
                printf("%2dR",pReadingNode->key);
            }else{
                printf("%2dB",pReadingNode->key);
            }
            if(readingNodeRow != maxDepth){
                pNodesQueue[queueEnd] = pReadingNode->pChilds[kLeft];
                nodesRow[queueEnd] = readingNodeRow + 1;
                queueEnd = (queueEnd + 1) % queueSize;
                
                pNodesQueue[queueEnd] = pReadingNode->pChilds[kRight];
                nodesRow[queueEnd] = readingNodeRow + 1;
                queueEnd = (queueEnd + 1) % queueSize;
            }
        }else{
            printf(" n ");
            if(readingNodeRow != maxDepth){
                pNodesQueue[queueEnd] = NULL;
                nodesRow[queueEnd] = readingNodeRow + 1;
                queueEnd = (queueEnd + 1) % queueSize;
                pNodesQueue[queueEnd] = NULL;
                nodesRow[queueEnd] = readingNodeRow + 1;
                queueEnd = (queueEnd + 1) % queueSize;
            }
        }
        
        
    }
    printf("\n");
}

Side SideAsChild(const TreeNode *pAimNode){
    
    if(pAimNode == NULL){
        printf("ERROR:No Node Set\n");
        return 0;
    }
    if(pAimNode->pFather == NULL){
        printf("ERROR:Has no father\n");
        return 0;
    }
    
    if(pAimNode == pAimNode->pFather->pChilds[kLeft]){
        return kLeft;
    }else{
        return kRight;
    }
}

Side OtherSide(const Side kASide){
    if(kASide == kLeft){
        return kRight;
    }else{
        return kLeft;
    }
}

Color OtherColor(const Color kAColor){
    if(kAColor == kRed){
        return kBlack;
    }else{
        return kRed;
    }
}

TreeNode* GetUncleNode(const TreeNode *pAimNode){
    if(pAimNode == NULL){
        return NULL;
    }
    if(pAimNode->pFather == NULL){
        return NULL;
    }
    if(pAimNode->pFather->pFather == NULL){
        return NULL;
    }
    //Get the child of grandpa other than father,including NULL
    return pAimNode->pFather->pFather->pChilds[OtherSide(SideAsChild(pAimNode->pFather))];
}

TreeNode* GetBrotherNode(const TreeNode *pAimNode){
    if(pAimNode == NULL){
        return NULL;
    }
    if(pAimNode->pFather == NULL){
        return NULL;
    }
    return pAimNode->pFather->pChilds[OtherSide(SideAsChild(pAimNode))];
}

int RotateTreeNode(const TreeNode *kpRotateNode,const Side kRotateSide,TreeNode **ppTreeRoot){
    TreeNode* pRotateNode = (TreeNode*)kpRotateNode;
    if(pRotateNode == NULL || pRotateNode->pFather == NULL){
        printf("ERROR:Can not rotate %d\n",pRotateNode->key);
        return -1;
    }
    //Record old structure
    TreeNode* pOldGrandpaNode = pRotateNode->pFather->pFather;
    TreeNode* pOldFatherNode = pRotateNode->pFather;
    TreeNode* pMidChild = pRotateNode->pChilds[kRotateSide];
    Side oldFatherSide = 0;
    if(pOldGrandpaNode != NULL){
        oldFatherSide= SideAsChild(pOldFatherNode);
    }
    //Exchange aim's father and his father's father
    pRotateNode->pFather = pOldGrandpaNode;
    pOldFatherNode->pFather = pRotateNode;
    pRotateNode->pChilds[kRotateSide] = pOldFatherNode;
    if(pOldGrandpaNode != NULL){
        pOldGrandpaNode->pChilds[oldFatherSide] = pRotateNode;
    }else{//which means his father is the root
        if(pOldFatherNode == *ppTreeRoot){
            *ppTreeRoot = pRotateNode;
        }else{
            printf("ERROR:Rotate %d\n",pRotateNode->key);
        }
    }
    
    //Change the rotate-side child's father
    pOldFatherNode->pChilds[OtherSide(kRotateSide)] = pMidChild;
    if(pMidChild != NULL){
        pMidChild->pFather = pOldFatherNode;
    }
    PrintTree(*ppTreeRoot);
}

int BalanceHeavyNode(const TreeNode *kpStartNode,TreeNode **ppTreeRoot){

    TreeNode *pCurrentAdjustingNode = (TreeNode *)kpStartNode;
    while(1){//May need to adjust more than one time
        if(pCurrentAdjustingNode == NULL){
        printf("ERROR:Nothing to adjust\n");
        return 0;
        }

        if(pCurrentAdjustingNode->pFather == NULL){
            printf("Set %d as root and color it black\n",pCurrentAdjustingNode->key);
            pCurrentAdjustingNode->color = kBlack;
            *ppTreeRoot = pCurrentAdjustingNode;
            return 1;
        }

        if(pCurrentAdjustingNode->pFather->color == kBlack){
            printf("No need to adjust %d for its father black\n",pCurrentAdjustingNode->key);
            return 1;
        }
        
        TreeNode* pCurrentUncle = GetUncleNode(pCurrentAdjustingNode);
        Side currentSide = SideAsChild(pCurrentAdjustingNode);
        Side currentFatherSide = SideAsChild(pCurrentAdjustingNode->pFather);
        
        if(currentSide != currentFatherSide){
            printf("Have not the same side with father,so rotate %d to side %d\n",pCurrentAdjustingNode->key,currentFatherSide);
            RotateTreeNode(pCurrentAdjustingNode,currentFatherSide,&*ppTreeRoot);
            
            //Continue to adjust its father where is now as its child
            pCurrentAdjustingNode = pCurrentAdjustingNode->pChilds[currentFatherSide];
            continue;
        }
        
        if(pCurrentUncle == NULL || pCurrentUncle->color == kBlack){
            TreeNode* pOldFather = pCurrentAdjustingNode->pFather;
            TreeNode* pOldGrandpa = pOldFather->pFather;
            
            printf("Adjust balance by father,so rotate %d to side %d\n",
                   pCurrentAdjustingNode->pFather->key,
                   OtherSide(currentFatherSide));
            
            RotateTreeNode(pCurrentAdjustingNode->pFather,OtherSide(currentFatherSide),&*ppTreeRoot);
        
            printf("Change color of %d and %d\n",pOldFather->key,pOldGrandpa->key);
            pOldFather->color = OtherColor(pOldFather->color);
            pOldGrandpa->color = OtherColor(pOldGrandpa->color);
            return 1;
        }
        
        //pCurrentUncle != NULL && pCurrentUncle->color != Black
        //Change current father and uncle color to be black,and change grandpa color to be red
        printf("Reverse color of %d,%d and %d\n",
                   pCurrentAdjustingNode->pFather->key,
                   pCurrentUncle->key,
                   pCurrentAdjustingNode->pFather->pFather->key);
        
        pCurrentAdjustingNode->pFather->color = kBlack;
        pCurrentUncle->color = kBlack;
        pCurrentAdjustingNode->pFather->pFather->color = kRed;
        //Continue to adjust its grandpa
        pCurrentAdjustingNode = pCurrentAdjustingNode->pFather->pFather;
    }
    return -1;
}

int InsertKeyToRedBlackTree(const int kKey,TreeNode **ppTreeRoot){
    TreeNode *pSearchingNode = *ppTreeRoot;
    printf("Try to insert %d\n",kKey);
    if(pSearchingNode == NULL){
        *ppTreeRoot = GetANewTreeNode(kKey,kBlack);
        return 0;
    }
    
    while(1){
        if(pSearchingNode->key == kKey){//The tree already has the key
            return 0;
        }
        
        //Get side
        Side childSide = 0;
        if(pSearchingNode->key < kKey){
            childSide = kRight;
        }else{
            childSide = kLeft;
        }
        
        if(pSearchingNode->pChilds[childSide] == NULL){//Insert as child
            pSearchingNode->pChilds[childSide] = GetANewTreeNode(kKey,kRed);
            pSearchingNode->pChilds[childSide]->pFather = pSearchingNode;
            pSearchingNode = pSearchingNode->pChilds[childSide];
            break;
        }else{//Search deeper
            pSearchingNode = pSearchingNode->pChilds[childSide];
        }
    }
    PrintTree(*ppTreeRoot);
    printf("Start to adjust %d\n",kKey);
    BalanceHeavyNode(pSearchingNode,ppTreeRoot);
    printf("After adjust\n");
    PrintTree(*ppTreeRoot);
    return 1;
}

int BalanceLightNode(const TreeNode* kpAimNode,TreeNode **ppTreeRoot){//Without change the aiming node
    TreeNode* pCurrentAimNode = (TreeNode*) kpAimNode;
    printf("Try balance light node %d\n",kpAimNode->key);
    while(1){
        //To protect error
        if(pCurrentAimNode == NULL){
            printf("ERROR:kpAimNode == NULL\n");
            return -1;
        }
        if(pCurrentAimNode->color == kRed){
            printf("(s0)Set current node %d to black\n",pCurrentAimNode->key);
            pCurrentAimNode->color = kBlack;
            return -1;
        }

        TreeNode* pAimInitFather = pCurrentAimNode->pFather;
        if(pAimInitFather == NULL){
            printf("(s1)pCurrentAimNode is root,no need to balance\n");
            return 1;
        }
    
        Side aimSide = SideAsChild(pCurrentAimNode);
        
        TreeNode* pAimInitBrother = GetBrotherNode(pCurrentAimNode);
        if(pAimInitBrother == NULL){
            printf("ERROR:GetBrotherNode(pCurrentAimNode) == NULL\n");
            return -1;
        }

        TreeNode* pAimInitBrotherChilds[2];
        pAimInitBrotherChilds[kLeft] = pAimInitBrother->pChilds[kLeft];
        pAimInitBrotherChilds[kRight] = pAimInitBrother->pChilds[kRight];

        if(pAimInitFather->color == kBlack
           && pAimInitBrother->color == kBlack
           && (pAimInitBrotherChilds[kLeft] == NULL || pAimInitBrotherChilds[kLeft]->color == kBlack)
           && (pAimInitBrotherChilds[kRight] == NULL || pAimInitBrotherChilds[kRight]->color == kBlack)
          ){
            printf("(s2)Set color of %d red\n",pAimInitBrother->key);
            pAimInitBrother->color = kRed;
            pCurrentAimNode = pAimInitFather;
            continue;
        }
        
        if(pAimInitFather->color == kRed
           && pAimInitBrother->color == kBlack
           && (pAimInitBrotherChilds[kLeft] == NULL || pAimInitBrotherChilds[kLeft]->color == kBlack)
           && (pAimInitBrotherChilds[kRight] == NULL || pAimInitBrotherChilds[kRight]->color == kBlack)
          ){
            printf("(s3)Exchange color of %d and %d\n",pAimInitBrother->key,pAimInitFather->key);
            pAimInitBrother->color = kRed;
            pAimInitFather->color = kBlack;
            return 1;
        }
        
        if(pAimInitFather->color == kBlack
           && pAimInitBrother->color == kRed
          ){
            printf("(s4)Rotate %d to side %d\n",pAimInitBrother->key,OtherSide(aimSide));
            RotateTreeNode(pAimInitBrother,OtherSide(aimSide),&*ppTreeRoot);
            printf("(s4)Set %d color black\n",pAimInitBrother->key);
            printf("(s4)Set %d color red\n",pAimInitFather->key);
            pAimInitBrother->color = kBlack;
            pAimInitFather->color = kRed;
            continue;
        }
        
        if(pAimInitBrotherChilds[aimSide] != NULL
           && pAimInitBrotherChilds[aimSide]->color ==kRed
           && (pAimInitBrotherChilds[OtherSide(aimSide)] == NULL || pAimInitBrotherChilds[OtherSide(aimSide)]->color == kBlack)
          ){
            printf("(s5)Rotate %d to side %d\n",pAimInitBrotherChilds[aimSide]->key,OtherSide(aimSide));
            RotateTreeNode(pAimInitBrotherChilds[aimSide],OtherSide(aimSide),&*ppTreeRoot);
            
            printf("(s5)Rotate %d to side %d\n",pAimInitBrotherChilds[aimSide]->key,aimSide);
            RotateTreeNode(pAimInitBrotherChilds[aimSide],aimSide,&*ppTreeRoot);
            
            printf("(s5)Set %d color black\n",pAimInitBrotherChilds[aimSide]->key);
            pAimInitBrotherChilds[aimSide]->color = kBlack;
            
            if(pAimInitFather->color == kRed){
                printf("(s5)Set %d color black\n",pAimInitFather->key);
                pAimInitFather->color = kBlack;
            }
            return 1;
        }
        
        if(pAimInitBrotherChilds[OtherSide(aimSide)] != NULL
           && pAimInitBrotherChilds[OtherSide(aimSide)]->color == kRed
          ){
            printf("(s6)Rotate %d to side %d\n",pAimInitBrother->key,aimSide);
            RotateTreeNode(pAimInitBrother,aimSide,&*ppTreeRoot);
            
            printf("(s6)Set %d color black\n",pAimInitBrotherChilds[OtherSide(aimSide)]->key);
            pAimInitBrotherChilds[OtherSide(aimSide)]->color = kBlack;
            
            if(pAimInitFather->color == kRed){
                printf("(s6)Set %d color black\n",pAimInitFather->key);
                pAimInitFather->color = kBlack;
                printf("(s6)Set %d color red\n",pAimInitBrother->key);
                pAimInitBrother->color = kRed;
            }
            return 1;
        }
        //ERROR Situation
        printf("ERROR:Other situation\n");
        return -1;
    }
}

int DeleteKeyFromRedBlackTree(const int kKey,TreeNode **ppTreeRoot){
    printf("Try to delete %d\n",kKey);
    TreeNode *aimNode = SearchTreeByKey(kKey,*ppTreeRoot);
    if(aimNode == NULL){
        printf("Can not find %d to delete\n",kKey);
        return -1;
    }
    
    //Decide to choose from successor or predecessor
    Side sideMode = 0;
    if(aimNode->pChilds[kRight] != NULL){
        sideMode = kRight;
    }else{
        sideMode = kLeft;
    }
    
    //To find the replacing node to be aimNode
    TreeNode *replacementNode = aimNode->pChilds[sideMode];
    while(replacementNode->pChilds[OtherSide(sideMode)] != NULL){
        replacementNode = replacementNode->pChilds[OtherSide(sideMode)];
    }
    //transfer the content without color from replacementNode to aimNode
    printf("Found %d to replace %d\n",replacementNode->key,aimNode->key);
    aimNode->key = replacementNode->key;
    aimNode = replacementNode;
    
    int isRoot = 0;
    int needLaterDeletion = 0;
    TreeNode *toBalanceNode = NULL;
    if(aimNode->pChilds[sideMode] != NULL){
        toBalanceNode = aimNode->pChilds[sideMode];
        aimNode->pChilds[sideMode]->pFather = aimNode->pFather;
        if(aimNode->pFather != NULL){
            aimNode->pFather->pChilds[OtherSide(sideMode)] = aimNode->pChilds[sideMode];
        }else{
            isRoot = 1;
        }
    }else{
        needLaterDeletion = 1;
        toBalanceNode = aimNode;
    }
    
    if(!isRoot){
        BalanceLightNode(toBalanceNode,ppTreeRoot);
        if(needLaterDeletion){
            aimNode->pFather->pChilds[SideAsChild(aimNode)] = NULL;
        }
        FreeTreeNode(&aimNode);
    }else{
        FreeTreeNode(&*ppTreeRoot);
    }
   
    printf("After delete %d:\n",kKey);
    PrintTree(*ppTreeRoot);
    return 0;
}

int main(){
    TreeNode *root = NULL;
    InsertKeyToRedBlackTree(15,&root);
    InsertKeyToRedBlackTree(10,&root);
    InsertKeyToRedBlackTree(20,&root);
    InsertKeyToRedBlackTree(30,&root);
    InsertKeyToRedBlackTree(40,&root);
    InsertKeyToRedBlackTree(50,&root);
    InsertKeyToRedBlackTree(60,&root);
    InsertKeyToRedBlackTree(80,&root);
    InsertKeyToRedBlackTree(35,&root);
    InsertKeyToRedBlackTree(66,&root);
    InsertKeyToRedBlackTree(65,&root);
    InsertKeyToRedBlackTree(88,&root);
    InsertKeyToRedBlackTree(77,&root);
    DeleteKeyFromRedBlackTree(30,&root);
    return 0;
}

3. 测试运行结果

Try to insert 15
Try to insert 10
   15B
10R     n 
Start to adjust 10
No need to adjust 10 for its father black
After adjust
   15B
10R     n 
Try to insert 20
   15B
10R    20R
Start to adjust 20
No need to adjust 20 for its father black
After adjust
   15B
10R    20R
Try to insert 30
            15B
   10R          20R
 n      n      n     30R
Start to adjust 30
Reverse color of 20,10 and 15
Set 15 as root and color it black
After adjust
            15B
   10B          20B
 n      n      n     30R
Try to insert 40
                              15B
            10B                      20B
    n            n            n           30R
 n      n      n      n      n      n      n     40R
Start to adjust 40
Adjust balance by father,so rotate 30 to side 0
            15B
   10B          30R
 n      n     20B    40R
Change color of 30 and 20
After adjust
            15B
   10B          30B
 n      n     20R    40R
Try to insert 50
                              15B
            10B                      30B
    n            n           20R          40R
 n      n      n      n      n      n      n     50R
Start to adjust 50
Reverse color of 40,20 and 30
No need to adjust 30 for its father black
After adjust
                              15B
            10B                      30R
    n            n           20B          40B
 n      n      n      n      n      n      n     50R
Try to insert 60
                                                                  15B
                              10B                                              30R
             n                        n                       20B                      40B
    n            n            n            n            n            n            n           50R
 n      n      n      n      n      n      n      n      n      n      n      n      n      n      n     60R
Start to adjust 60
Adjust balance by father,so rotate 50 to side 0
                              15B
            10B                      30R
    n            n           20B          50R
 n      n      n      n      n      n     40B    60R
Change color of 50 and 40
After adjust
                              15B
            10B                      30R
    n            n           20B          50B
 n      n      n      n      n      n     40R    60R
Try to insert 80
                                                                  15B
                              10B                                              30R
             n                        n                       20B                      50B
    n            n            n            n            n            n           40R          60R
 n      n      n      n      n      n      n      n      n      n      n      n      n      n      n     80R
Start to adjust 80
Reverse color of 60,40 and 50
Adjust balance by father,so rotate 30 to side 0
                              30R
            15B                      50R
   10B          20B          40B          60B
 n      n      n      n      n      n      n     80R
Change color of 30 and 15
After adjust
                              30B
            15R                      50R
   10B          20B          40B          60B
 n      n      n      n      n      n      n     80R
Try to insert 35
                              30B
            15R                      50R
   10B          20B          40B          60B
 n      n      n      n     35R     n      n     80R
Start to adjust 35
No need to adjust 35 for its father black
After adjust
                              30B
            15R                      50R
   10B          20B          40B          60B
 n      n      n      n     35R     n      n     80R
Try to insert 66
                                                                  30B
                              15R                                              50R
            10B                      20B                      40B                      60B
    n            n            n            n           35R           n            n           80R
 n      n      n      n      n      n      n      n      n      n      n      n      n      n     66R     n 
Start to adjust 66
Have not the same side with father,so rotate 66 to side 1
                                                                  30B
                              15R                                              50R
            10B                      20B                      40B                      60B
    n            n            n            n           35R           n            n           66R
 n      n      n      n      n      n      n      n      n      n      n      n      n      n      n     80R
Adjust balance by father,so rotate 66 to side 0
                              30B
            15R                      50R
   10B          20B          40B          66R
 n      n      n      n     35R     n     60B    80R
Change color of 66 and 60
After adjust
                              30B
            15R                      50R
   10B          20B          40B          66B
 n      n      n      n     35R     n     60R    80R
Try to insert 65
                                                                  30B
                              15R                                              50R
            10B                      20B                      40B                      66B
    n            n            n            n           35R           n           60R          80R
 n      n      n      n      n      n      n      n      n      n      n      n      n     65R     n      n 
Start to adjust 65
Have not the same side with father,so rotate 65 to side 0
                                                                  30B
                              15R                                              50R
            10B                      20B                      40B                      66B
    n            n            n            n           35R           n           65R          80R
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n      n      n 
Reverse color of 65,80 and 66
Reverse color of 50,15 and 30
Set 30 as root and color it black
After adjust
                                                                  30B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n           35R           n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n      n      n 
Try to insert 88
                                                                  30B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n           35R           n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n      n     88R
Start to adjust 88
No need to adjust 88 for its father black
After adjust
                                                                  30B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n           35R           n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n      n     88R
Try to insert 77
                                                                  30B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n           35R           n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n     77R    88R
Start to adjust 77
No need to adjust 77 for its father black
After adjust
                                                                  30B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n           35R           n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n     77R    88R
Try to delete 30
Found 35 to replace 30
Try balance light node 35
(s0)Set current node 35 to black
After delete 30:
                                                                  35B
                              15B                                              50B
            10B                      20B                      40B                      66R
    n            n            n            n            n            n           65B          80B
 n      n      n      n      n      n      n      n      n      n      n      n     60R     n     77R    88R

Leave a Comment