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