实现一个红黑树
原创实现一个红黑树
原创
红黑树
在数据结构中，如果提到编码和压缩绕不开 Hoffman 树，如果从快速获取搜索的树结构那么就离不开红黑树，哈希表设计中，从数组加链表，不行我就数组加红黑树，大名鼎鼎的 epoll 也开始起了红黑树。
红黑树的规定很是难以理解，其他的五大特性如下：
- 每个结点是红的或者黑的
- 根结点是黑的
- 每个叶子结点是黑的
- 如果一个结点是红的，则它的两个儿子都是黑的
- 对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点
当然面对这样的定义很多人其实会很困惑，他为什么要这样规定，这样其实是学术上的事情，研究这种东西的人都有一定算法规则，在这方面多做深究其实意义不大。
代码实现
有了定义，那就废话不多说，从代码开始讲起。
数据结构
首先就是我们需要定义红黑树这样的数据结构，首先就是我们需要定义红黑树的每个节点的情况。
#define RED 1
#define BLACK 2
typedef int KEY_TYPE;
typedef struct _rbtree_node {
unsigned char color; //颜色
struct _rbtree_node *right; //右节点
struct _rbtree_node *left; //左节点
struct _rbtree_node *parent; //父节点
KEY_TYPE key; //保存的 key
void *value; //保存的value
} rbtree_node;上述结构体比较简单，跟普通的二叉树相比多了一个颜色，多了一个父节点指针。
红黑树结构体如下：
typedef struct _rbtree {
rbtree_node *root; //红黑树根节点
rbtree_node *nil; //红黑树的空节点
} rbtree;左旋和右旋
树的基本操作就是旋转，而旋转也有左旋和右旋，而红黑树的很多内容也是基于这两个操作来的。
我们先来看左旋，我们来看发生了什么变化。
首先就是 x 的父节点，他指向了 y。
然后就是 x 节点，他的父节点变成了 y，他的右节点指向 y 的左节点。
最后就是 y 节点，他的左节点变成了 x ，父节点变成了 x 的父节点。
所以我们可以写如下代码：
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right
x->right = y->left; //1 1
if (y->left != T->nil) { //1 2
y->left->parent = x;
}
y->parent = x->parent; //1 3
if (x->parent == T->nil) { //1 4
T->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; //1 5
x->parent = y; //1 6
}代码较为简单，就是做了一点校验。
然后再看右旋
同上可以得出：
x 是 y 的左节点
y 的父节点指向了x
y 的父节点指向了 x ，y 的左节点指向了 x 的右节点
x 的 右节点指向了 x 父节点指向 y 的父节点。
因此代码实现如下：
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
rbtree_node *x = y->left;
y->left = x->right;
if (x->right != T->nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == T->nil) {
T->root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}功能实现
树的旋转功能做好之后就是也好做树的基本功能了，增删查遍历功能，树基本很少有改这种功能，查和遍历较为简单，因此直接是实现。
红黑树查的功能如下：
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {
rbtree_node *node = T->root;
while (node != T->nil) {
if (key < node->key) {
node = node->left;
} else if (key > node->key) {
node = node->right;
} else {
return node;
}
}
return T->nil;
}上述实现较为简单，类似二分查找法。
而遍历的功能实现如下：
void rbtree_traversal(rbtree *T, rbtree_node *node) {
if (node != T->nil) {
rbtree_traversal(T, node->left);
printf("key:%d, color:%d\n", node->key, node->color);
rbtree_traversal(T, node->right);
}
}使用了中序遍历的方式进行了遍历。
红黑树添加
对于红黑树，添加，我们默认这样的规则，我们添加的节点是红色节点。
首先我们讨论
1、添加的节点父节点是红色的，而叔父节点也是红色的，而且父节点是祖父节点的左子树。
图中要插入 z ，y 是 z 的叔父节点，这种情况下父节点变成黑树，祖父节点变成红色即可。
2、当前的父节点是祖父节点左子树，叔父节点是黑色的，而当前节点是父节点的右子树时候，需要如下：
我们需要的操作就是以当前节点父节点为轴左旋。
左旋之后，我们当前的父节点是祖父节点左子树，叔父节点是黑色，当前节点是父节点左子树的时候需要以祖父节点为轴进行右旋
上述只是父节点都是红色的，后边如果继续讨论篇幅很大，但是有了上边大概概念，跟着代码大概就能猜出什么情况下应该怎么做了。
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
while (z->parent->color == RED) { //父节点是红色
if (z->parent == z->parent->parent->left) { //父节点是左子树
rbtree_node *y = z->parent->parent->right; //叔父节点
if (y->color == RED) { //叔父节点是红色
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //将父节点和叔父节点置为黑色，祖父节点置为红色，然后再从祖父节点开始向上调整
} else { //叔父节点是黑色
if (z == z->parent->right) {//当前节点是父节点右子树
z = z->parent; //以父节点为轴进行左旋
rbtree_left_rotate(T, z);
}
z->parent->color = BLACK; //父节点置为黑色
z->parent->parent->color = RED; //祖父置为红色
rbtree_right_rotate(T, z->parent->parent); //以祖父为轴进行右旋
}
}else { //父节点是右子树
rbtree_node *y = z->parent->parent->left; //叔父节点
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //叔父节点是红色
} else {
if (z == z->parent->left) {
z = z->parent;
rbtree_right_rotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_left_rotate(T, z->parent->parent);
}
}
}
T->root->color = BLACK;
}上述红黑树增加节点的大概方向，但是实际添加需要对红黑树各种边界做出判断，因此需要定义如下几个函数。
rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
while (x->left != T->nil) {
x = x->left;
}
return x;
}该函数能找出某个节点最左的子节点，当然如果我们默认红黑树按顺序排列，那这个节点就是以 x 为根节点的最小值。
rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
while (x->right != T->nil) {
x = x->right;
}
return x;
}同理，这是最大值。
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
rbtree_node *y = x->parent;
if (x->right != T->nil) { //找出了整个红黑树中比 x 大的最小值
return rbtree_mini(T, x->right);
}
while ((y != T->nil) && (x == y->right)) { //没有右子树而且本身是右子树，没有找到比他大的节点
x = y;
y = y->parent; //不断向上找
}
return y; //返回比 x 大的最小值
}而整体的插入就是如下：
void rbtree_insert(rbtree *T, rbtree_node *z) {
rbtree_node *y = T->nil;
rbtree_node *x = T->root;
while (x != T->nil) { //遍历红黑树找到可以插入的节点
y = x;
if (z->key < x->key) {
x = x->left;
} else if (z->key > x->key) {
x = x->right;
} else { //Exist
return ;
}
}
z->parent = y;
if (y == T->nil) {
T->root = z; //插入父节点
} else if (z->key < y->key) {
y->left = z; //插入左节点
} else {
y->right = z;
}
z->left = T->nil; //设置为红色节点
z->right = T->nil;
z->color = RED;
rbtree_insert_fixup(T, z); //不断向上调整
}删除节点
还是如先前讨论。
1、当前节点兄弟节点是红节点。
如图，删除 786 节点后，以父节点为轴进行旋转，建立再当前节点没有左右子树。
2、当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的
这是将兄弟节点和叔父节点设置为红色即可。
3、当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的或者兄弟结点的右孩子是红色的
图中情况当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的，以兄弟节点为轴进行左旋。
当当前结点的兄弟结点是黑色的，兄弟结点的右孩子是红色的，以当前节点父节点为轴进行右旋。
实现代码如下：
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {
while ((x != T->root) && (x->color == BLACK)) { //当前节点是黑色，而且不是根节点
if (x == x->parent->left) { //要删除节点是父节点左子树
rbtree_node *w= x->parent->right; //右子树
if (w->color == RED) { //兄弟节点是红色
w->color = BLACK;
x->parent->color = RED; //父节点设为红色
rbtree_left_rotate(T, x->parent); //左旋
w = x->parent->right;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) { //左右节点颜色都是黑色
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) { //右边是黑色，左边是红色
w->left->color = BLACK;
w->color = RED;
rbtree_right_rotate(T, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rbtree_left_rotate(T, x->parent);
x = T->root;
}
} else {
rbtree_node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rbtree_right_rotate(T, x->parent);
w = x->parent->left;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rbtree_left_rotate(T, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rbtree_right_rotate(T, x->parent);
x = T->root;
}
}
}
x->color = BLACK;
}上述描述其实较为简单，实际删除需要如下代码：
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {
rbtree_node *y = T->nil;
rbtree_node *x = T->nil;
if ((z->left == T->nil) || (z->right == T->nil)) {
y = z;
} else {
y = rbtree_successor(T, z);
}
if (y->left != T->nil) {
x = y->left;
} else if (y->right != T->nil) {
x = y->right;
}
x->parent = y->parent;
if (y->parent == T->nil) {
T->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
if (y != z) {
z->key = y->key;
z->value = y->value;
}
if (y->color == BLACK) {
rbtree_delete_fixup(T, x);
}
return y;
}跟添加节点一样，就不多分析。
结语
红黑树的操作其实较为死板和公式化，只不过需要考虑的分支较多，只要仔细深入各个分支进行写代码就很简单。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
