首先红黑树是一种平衡树,通过红黑染色的方式保持平衡
由以上四个限制可以得到以下性质:
the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf
这个结果很容易想到,根节点到达每个叶节点上的黑色节点数一样,那么最长路径和最短路径之间的节点数量差别只有红色节点,而红色节点不能连续出现(由限制3)可知),所以最长路径最多是最短路径的两倍(红黑交替和全黑)
这就使得红黑树能够维持一个高平衡性,保证了最长路径和最短路径的差值不会太大
在具体学习红黑树的代码之前,我们先看一下Linux源码中对红黑树使用的文档和代码:
struct mytype *my_search(struct rb_root *root, char *string)
{
struct rb_node *node = root->rb_node;
while (node) {
struct mytype *data = container_of(node, struct mytype, node);
int result;
result = strcmp(string, data->keystring);
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
其中用到的数据结构定义如下:
struct rb_root {
struct rb_node *rb_node;
};
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
};
struct mytype {
struct rb_node node;
char *keystring;
};
然后我们看一下 container_of 的定义:
#define container_of(ptr, type, member)
({
const typeof(((type*)0)->member)* __mptr = (ptr);
(type*)((char*)__mptr - offsetof(type, member));
})
宏的作用是:
接收指向一个对象(数据)的指针,这个数据所属于的结构体的类型,以及这个数据在结构体中的成员名,返回指向这个结构体的指针
简而言之就是取容器
所以 container_of(node, struct mytype, node)这个宏的作用就是从 node这个属于红黑树部分的结构体,获得它的容器,从而得到具体的数据
这里 container_of()的原理是通过计算指定成员的偏移量,以及其地址,计算出包含它的结构的地址
这里采用了类似装饰器的想法,mytype把红黑树节点包起来,使得数据可以和红黑树分开单独编写逻辑,这是在没有类和模板之类的东西的C语言下对代码复用的一种实现
知道这一部分的设计思想后,搜索部分就是简单的BST的搜索过程,由于储存的是字符串,所以使用 strcmp()来比较数据的大小
下面是插入操作的代码:
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);
int result = strcmp(data->keystring, this->keystring);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return FALSE;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return TRUE;
}
在寻找插入节点部分和一般的BST一样,找到插入位置后使用 rb_link_node()将节点插入到红黑树中,然后使用 rb_insert_color()来维护红黑树的性质(之前提到的四条规则)
关于如何维护红黑树的性质及其具体代码,我们在后面的实现中再讨论
删除操作和替换操作是Linux中自带实现的,只需要调用函数即可:
void rb_erase(struct rb_node *victim, struct rb_root *tree);
void rb_replace_node(struct rb_node *old, struct rb_node *new,
struct rb_root *tree);
只要找到了指定的节点,就可以通过这两个函数来删除或者替换节点
struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);
这四个函数可以在任意一棵红黑树中找到最小值、最大值、后继、前驱
相关的操作在BST中都会介绍到
现在知道了红黑树的限制,我们的工作就是如何让BST的操作能够满足上面的四个性质,下面我们一个个操作来说:
(这里采用的是wikipedia的代码,linux的代码我们最后再看)
首先请记住上图第一张中的N、P、S、C、D节点的位置,本文来自我的学习笔记,所以并没有很多配图,红黑树的核心操作就来源于这五个节点的变化,请对号入座
首先关于红黑树所使用的结构如下:
enum color_t { BLACK, RED };
struct RBnode { // node of red–black tree
RBnode* parent; // == NIL if root of the tree
RBnode* child[2]; // == NIL if child is empty
// The index is:
// LEFT := 0, if (key < parent->key)
// RIGHT := 1, if (key > parent->key)
enum color_t color;
int key;
};
#define NIL NULL // null pointer or pointer to sentinel node
#define LEFT 0
#define RIGHT 1
#define left child[LEFT]
#define right child[RIGHT]
struct RBtree { // red–black tree
RBnode* root; // == NIL if tree is empty
};
首先我们要插入一个新的节点,通过一般BST的方式找到该节点对应的位置:
RBnode** find_place(RBtree* tree, int key) {
RBnode** node = &tree->root;
while (*node != nullptr) {
if (key < (*node)->key)
node = &(*node)->left;
else if (key > (*node)->key)
node = &(*node)->right;
else
return nullptr;
}
}
这里和Linux源码一样使用了指针的指针,用来得到结构 RBnode的中指针 left和 right,这样能够方便直接修改一个节点的父节点
找到这个节点的位置后我么可以直接将其插入红黑树,为了维持红黑树的第四性质:
Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
我们默认插入的节点为红色,并且检测当前的节点的case
这里的case指的是一个节点附近和它相连的一系列节点的构成情况,是否构成一个违反红黑树性质的情况
我们把插入后的情况检查分为6种:
插入的节点的父节点是黑色,此时红黑树性质不被破坏,不做任何改动
如果P节点和U节点都是红色,那么祖父节点一定是黑色,为了维护红黑树,我们需要把P和U节点染成黑色,然后把G节点染成红色,这样局部满足了红黑树性质
同时,为了让祖父节点不破坏role3,我们把N节点设置为G,然后循环这个过程,直到N节点为空,或者构成不需要修改的情况
如果插入的节点为根节点,则不需要改动
如果插入的父节点是红色且为根节点,则改变父节点的颜色为黑色即可
上述四种情况都很简单,代码如下:
void RBinsert1(RBtree* T, // -> red–black tree
struct RBnode* N, // -> node to be inserted
struct RBnode* P, // -> parent node of N ( may be NULL )
byte dir) // side ( LEFT or RIGHT ) of P where to insert N
{
struct RBnode* G; // -> parent node of P
struct RBnode* U; // -> uncle of N
N->color = RED;
N->left = NIL;
N->right = NIL;
N->parent = P;
if (P == NULL) { // There is no parent
T->root = N; // N is the new root of the tree T.
return; // insertion complete
}
P->child[dir] = N; // insert N as dir-child of P
// start of the (do while)-loop:
do {
if (P->color == BLACK) {
// Case_I1 (P black):
return; // insertion complete
}
// From now on P is red.
if ((G = P->parent) == NULL)
goto Case_I4; // P red and root
// else: P red and G!=NULL.
dir = childDir(P); // the side of parent G on which node P is located
U = G->child[1 - dir]; // uncle
if (U == NIL || U->color == BLACK) // considered black
goto Case_I56; // P red && U black
// Case_I2 (P+U red):
P->color = BLACK;
U->color = BLACK;
G->color = RED;
N = G; // new current node
// iterate 1 black level higher
// (= 2 tree levels)
} while ((P = N->parent) != NULL);
// end of the (do while)-loop
wikipedia的代码和Linux源码实现的代码架构不太一样
这里的代码将数据包含在节点类中,我们通过迭代找到需要插入位置的父节点,然后通过 dir来确定插入的方向,然后直接将 N接到 P的后面
同时设置 N的默认颜色为红色等
接下来我们进入case 5和6,首先我们已经确定P节点为红色,然后U节点为黑色,这样我们就不能通过染色解决问题,这样不能两边同时改变黑色节点数量(我们接下来称为Black height)
红黑树选择的解决方式如下:
如果不能满足以上要求的话,进入case 5:
这样我们就构建出了一个case 6:
此时我们发现一个问题,旋转操作是会改变RBtree的Black Height的,简单列举几种情况即可发现这个问题
但是这里旋转的两个节点都是红色节点,所以对于Black Height并没有影响,但是对于case 6而言,我们就需要对黑色节点进行旋转了
这么一来,插入的6种case就考虑完毕了,下面是case 5、6的代码部分:
if (N == P->child[1 - dir]) { // Case_I5 (P red && U black && N inner
// grandchild of G):
RotateDir(P, dir); // P is never the root
N = P; // new current node
P = G->child[dir]; // new parent of N
// fall through to Case_I6
}
// Case_I6 (P red && U black && N outer grandchild of G):
RotateDirRoot(T, G, 1 - dir); // G may be the root
P->color = BLACK;
G->color = RED;
return; // insertion complete
// end of RBinsert1
删除操作的简单情况:
对于一个只有一个子节点的红色节点,由于一定没有子节点,所以我们可以直接删除这个节点
对于只有一个子节点的黑色节点,其子节点一定是红色,我们可以将其直接替换删除节点,然后将其染为黑色,从而满足Role 4
考虑了只有一个子节点和根节点的简单情况后,我们来考虑有两个子节点的情况:
前驱或后继节点一定是只有一个子节点,或者本身就是叶子节点,所以至此我们只剩下最后一种情况:
如果一个黑色节点没有子节点,我们将其删除后必然会破坏Role 4,此时需要进行删除后的红黑树维护
删除后操作我们总共要关注5个节点的情况:
S、 N、P、C和 D节点
如果删除的黑色节点是一个新的根节点,那么直接删除即可
Case_D1 (P == NULL):
return; // deletion complete
C和 D节点我们认为是 S节点的子节点
S节点是 N节点的兄弟节点,当 S节点和 P节点都是黑色,且C和 D节点也是黑色时,采取以下操作:
void RBdelete2(
RBtree* T, // -> red–black tree
struct RBnode* N) // -> node to be deleted
{
struct RBnode* P = N->parent; // -> parent node of N
byte dir; // side of P on which N is located ( { LEFT, RIGHT })
struct RBnode* S; // -> sibling of N
struct RBnode* C; // -> close nephew
struct RBnode* D; // -> distant nephew
// P != NULL, since N is not the root.
dir = childDir(N); // side of parent P on which the node N is located
// Replace N at its parent P by NIL:
P->child[dir] = NIL;
goto Start_D; // jump into the loop
// start of the (do while)-loop:
do {
dir = childDir(N); // side of parent P on which node N is located
Start_D:
S = P->child[1-dir]; // sibling of N (has black height >= 1)
D = S->child[1-dir]; // distant nephew
C = S->child[ dir]; // close nephew
if (S->color == RED)
goto Case_D3; // S red ===> P+C+D black
// S is black:
if (D != NIL && D->color == RED) // not considered black
goto Case_D6; // D red && S black
if (C != NIL && C->color == RED) // not considered black
goto Case_D5; // C red && S+D black
// Here both nephews are == NIL (first iteration) or black (later).
if (P->color == RED)
goto Case_D4; // P red && C+S+D black
// Case_D2 (P+C+S+D black):
S->color = RED;
N = P; // new current node (maybe the root)
// iterate 1 black level
// (= 1 tree level) higher
} while ((P = N->parent) != NULL);
// end of the (do while)-loop
来自Wikipedia的伪代码,有着详细的注释
若 S节点是红色节点,C和 D是黑色节点,进行以下操作:
Case_D3: // S red && P+C+D black:
RotateDirRoot(T,P,dir); // P may be the root
P->color = RED;
S->color = BLACK;
S = C; // != NIL
// now: P red && S black
D = S->child[1-dir]; // distant nephew
if (D != NIL && D->color == RED)
goto Case_D6; // D red && S black
C = S->child[ dir]; // close nephew
if (C != NIL && C->color == RED)
goto Case_D5; // C red && S+D black
// Otherwise C+D considered black.
// fall through to Case_D4
这样一来,我们要考虑的case就变成了:N黑,P红,S黑
接下来我们要考虑的case就是 C和 D节点的不同情况:
如果 D和 C都是黑色,那么将 S染为红色,将 P染为黑色,这样相当于给右子树的Black height加一,直接完成了红黑树的维护
Case_D4: // P red && S+C+D black:
S->color = RED;
P->color = BLACK;
return; // deletion complete
我们认为 C节点是左子节点,D节点是右子节点
如果 C节点为红色,不管 P节点是黑还是红,我们都可以直接执行下面的操作:
Case_D5: // C red && S+D black:
RotateDir(S,1-dir); // S is never the root
S->color = RED;
C->color = BLACK;
D = S;
S = C;
// now: D red && S black
// fall through to Case_D6
这么一来,红色就从 C节点转移到了 D节点的位置上,于是我们进入了最后的case 6
此时的 D节点是红色,不管 P节点是黑还是红,我们都可以直接执行下面的操作:
Case_D6: // D red && S black:
RotateDirRoot(T,P,dir); // P may be the root
S->color = P->color;
P->color = BLACK;
D->color = BLACK;
return; // deletion complete
} // end of RBdelete2
到此为止,基本的红黑树过程已经阐述完毕,我们下面总结一下红黑树的这些操作到底在干什么,问什么要这样干
首先要提及的就是旋转操作,旋转操作我们可以看作一个子节点(N)和一个父节点(P)交换位置
对于图中的三个框起来的子树部分,旋转操作的影响如下:
结合起 P和 S这两个旋转对象的颜色,旋转操作可以在不改变BST性质的情况下改变 N子树和 D子树Black height,这是旋转操作在红黑树维护中扮演的角色
但是旋转会改变Black height,也有可能将红色的 C节点接到红色的 P节点上,所以一般旋转后还需要重新进行染色
于是我们重新来审视以下删除后的维护过程为什么要这么做:
首先可以直接处理完毕的case有:
合理地使用旋转和染色可以用来操控子树的Black Height,另外的三种情况就是想办法把旋转操作的五个关键节点变成可以直接处理的情况
为什么不能直接染色更改?
直接修改成红色可能打破role 3,所以通过旋转后,保证了修改节点的子节点一定是黑色,然后再修改颜色
到这里红黑树的基本思想已经介绍完成了
完全把这些情况和旋转、染色的意义理清楚还是花费了超出想象的篇幅,所以关于Linux源码的部分暂且就不再看了,其实现的原理都是基于红黑树罢
页面更新:2024-04-22
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号