在之前，我曾经给出过一份红黑树的实现代码，很多人提出异议，说是代码有问题，我曾经做过一些测试，貌似都没有出错，因为这份代码是在我学习红黑树之后很久才贴出来的，所以后来没有再仔细看这份代码。
最近，因为工作上的原因，我需要使用红黑树结构，本以为拿来那份代码稍加改动就可以了，没想到代码调试了很久都还有问题，于是，我决定重新补习红黑树的知识，仔细查看了原有的代码，才发现是有问题的，在这里，给出修正版本的代码，希望这次是没有错误:) 请大家原谅我的疏忽。
我就不在原来的页面修改那份代码了，只是在上面加上说明那份代码是有错误的。
/*-----------------------------------------------------------
RB-Tree的插入和删除操作的实现算法
参考资料:
1) <<Introduction to algorithm>>
2) <<STL源码剖析>>
3) sgi-stl中stl_tree.h中的实现算法
4) http://epaperpress.com/sortsearch/index.html
5) http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
作者：李创 (http://www.cppblog.com/converse/)
您可以自由的传播，修改这份代码，转载处请注明原作者
红黑树的几个性质:
1) 每个结点只有红和黑两种颜色
2) 根结点是黑色的
3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
的数目相同
-------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int KEY;
enum NODECOLOR
{
BLACK = 0,
RED = 1
};
typedef struct RBTree
{
struct RBTree *parent;
struct RBTree *left, *right;
KEY key;
NODECOLOR color;
}RBTree, *PRBTree;
PRBTree RB_InsertNode(PRBTree root, KEY key);
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z);
PRBTree RB_DeleteNode(PRBTree root, KEY key);
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x , PRBTree x_parent);
PRBTree Find_Node(PRBTree root, KEY key);
void Left_Rotate(PRBTree A, PRBTree& root);
void Right_Rotate(PRBTree A, PRBTree& root);
void Mid_Visit(PRBTree T);
void Mid_DeleteTree(PRBTree T);
void Print_Node(PRBTree node);
/*-----------------------------------------------------------
| A B
| / \ ==> / \
| a B A y
| / \ / \
| b y a b
-----------------------------------------------------------*/
void Left_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->right;
A->right = B->left;
if (NULL != B->left)
B->left->parent = A;
B->parent = A->parent;
// 这样三个判断连在一起避免了A->parent = NULL的情况
if (A == root)
{
root = B;
}
else if (A == A->parent->left)
{
A->parent->left = B;
}
else
{
A->parent->right = B;
}
B->left = A;
A->parent = B;
}
/*-----------------------------------------------------------
| A B
| / \ / \
| B y ==> a A
| / \ / \
|a b b y
-----------------------------------------------------------*/
void Right_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->left;
A->left = B->right;
if (NULL != B->right)
B->right->parent = A;
B->parent = A->parent;
// 这样三个判断连在一起避免了A->parent = NULL的情况
if (A == root)
{
root = B;
}
else if (A == A->parent->left)
{
A->parent->left = B;
}
else
{
A->parent->right = B;
}
A->parent = B;
B->right = A;
}
/*-----------------------------------------------------------
| 函数作用:查找key值对应的结点指针
| 输入参数:根节点root,待查找关键值key
| 返回参数:如果找到返回结点指针,否则返回NULL
-------------------------------------------------------------*/
PRBTree Find_Node(PRBTree root, KEY key)
{
PRBTree x;
// 找到key所在的node
x = root;
do
{
if (key == x->key)
break;
if (key < x->key)
{
if (NULL != x->left)
x = x->left;
else
break;
}
else
{
if (NULL != x->right)
x = x->right;
else
break;
}
} while (NULL != x);
return x;
}
/*-----------------------------------------------------------
| 函数作用:在树中插入key值
| 输入参数:根节点root,待插入结点的关键值key
| 返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_InsertNode(PRBTree root, KEY key)
{
PRBTree x, y;
PRBTree z;
if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
{
printf("Memory alloc error\n");
return NULL;
}
z->key = key;
// 得到z的父节点, 如果KEY已经存在就直接返回
x = root, y = NULL;
while (NULL != x)
{
y = x;
if (key < x->key)
{
if (NULL != x->left)
{
x = x->left;
}
else
{
break;
}
}
else if (key > x->key)
{
if (NULL != x->right)
{
x = x->right;
}
else
{
break;
}
}
else
{
return root;
}
}
if (NULL == y || y->key > key)
{
if (NULL == y)
root = z;
else
y->left = z;
}
else
{
y->right = z;
}
// 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
z->parent = y;
z->left = z->right = NULL;
z->color = RED;
// 对红黑树进行修正
return RB_InsertNode_Fixup(root, z);
}
/*-----------------------------------------------------------
| 函数作用:对插入key值之后的树进行修正
| 输入参数:根节点root,插入的结点z
| 返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
PRBTree y;
while (root != z && RED == z->parent->color) // 当z不是根同时父节点的颜色是red
{
if (z->parent == z->parent->parent->left) // 父节点是祖父节点的左子树
{
y = z->parent->parent->right; // y为z的伯父节点
if (NULL != y && RED == y->color) // 伯父节点存在且颜色是red
{
z->parent->color = BLACK; // 更改z的父节点颜色是B
y->color = BLACK; // 更改z的伯父节点颜色是B
z->parent->parent->color = RED; // 更改z的祖父节点颜色是B
z = z->parent->parent; // 更新z为它的祖父节点
}
else // 无伯父节点或者伯父节点颜色是b
{
if (z == z->parent->right) // 如果新节点是父节点的右子树
{
z = z->parent;
Left_Rotate(z, root);
}
z->parent->color = BLACK; // 改变父节点颜色是B
z->parent->parent->color = RED; // 改变祖父节点颜色是R
Right_Rotate(z->parent->parent, root);
}
}
else // 父节点为祖父节点的右子树
{
y = z->parent->parent->left; // y为z的伯父节点
if (NULL != y && RED == y->color) // 如果y的颜色是red
{
z->parent->color = BLACK; // 更改父节点的颜色为B
y->color = BLACK; // 更改伯父节点的颜色是B
z->parent->parent->color = RED; // 更改祖父节点颜色是R
z = z->parent->parent; // 更改z指向祖父节点
}
else // y不存在或者颜色是B
{
if (z == z->parent->left) // 如果是父节点的左子树
{
z = z->parent;
Right_Rotate(z, root);
}
z->parent->color = BLACK; // 改变父节点的颜色是B
z->parent->parent->color = RED; // 改变祖父节点的颜色是RED
Left_Rotate(z->parent->parent, root);
}
}
} // while(RED == z->parent->color)
// 根节点的颜色始终都是B
root->color = BLACK;
return root;
}
/*-----------------------------------------------------------
| 函数作用:在树中删除key值
| 输入参数:根节点root,待插入结点的关键值key
| 返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_DeleteNode(PRBTree root, KEY key)
{
PRBTree x, y, z, x_parent;
// 首先查找需要删除的节点
z = Find_Node(root, key);
if (NULL == z)
return root;
y = z, x = NULL, x_parent = NULL;
// y是x按照中序遍历树的后继
if (NULL == y->left)
{
x = y->right;
}
else
{
if (NULL == y->right)
{
x = y->left;
}
else
{
y = y->right;
while (NULL != y->left)
y = y->left;
x = y->right;
}
}
if (y != z)
{
z->left->parent = y;
y->left = z->left;
if (y != z->right)
{
x_parent = y->parent;
if (NULL != x)
x->parent = y->parent;
y->parent->left = x;
y->right = z->right;
z->right->parent = y;
}
else
{
x_parent = y;
}
if (root == z)
{
root = y;
}
else if (z == z->parent->left)
{
z->parent->left = y;
}
else