在数据结构中,如果提到编码和压缩绕不开 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 删除。