0. 前言
前边Nginx中定时器的实现,以及Linux中完全公平算法都用了红黑树,是时候对它进行整理了。
红黑树是一种二叉平衡树,下边先来看看二叉搜索树,毕竟红黑树的用法与二叉树的用法基本是类似的;然后来看看红黑树的原理,为了更好的理解红黑树,我们对照2-3-4树来看;最后来看看红黑树的实现。
1. 二叉搜索树
定义:对于任何结点x,其左子树的关键字最大不超过x,其右子树的关键字最小不低于x。
每个结点,除了key和卫星数据之外,每个结点还包括left、right和p(parent)指针。
以下代码都是伪码
查找
-
遍历
遍历根据输出关键字的位置位于左子树和右子树的位置,可以分成中序遍历(inorder
)、前序遍历(preorder
)、后序遍历(postorder
)。
void inorderTreeWalk(x){
if(x != null){
inorderTreeWalk(x.left);
print(x.key);
inorderTreeWalk(x.right);
}
}
-
搜索
二叉搜索树就是为了查找设计的,过程如下:
TreeNode treeSearch(x, k){
if(x==null || k==x.key){
return x;
}
if(k < x.key)
return treeSearch(x.left, k);
else
return treeSearch(x.right, k);
}
除了递归的方式,还可以写成循环的方式:
TreeNode iterativeTreeSearch(x, k){
while (x!=null && k!=x.key){
if(k < x.key)
x = x.left;
else
x = x.right;
}
return x;
}
-
最大与最小节点
最小值是最左侧的节点,最大值最右侧的节点。
TreeNode treeMinimum(x){
while(x.left != null){
x = x.left;
}
return x;
}
TreeNode treeMaxium(x){
while (x.right != null){
x = x.right;
}
return x;
}
-
后继与前驱
后继(Successor)指的是比该节点大的元素中最小的;前驱(Predecessor)是比该节点小的中最大的。
如图:对于11而言,10是它的前继,12是它的后驱。但对于10而言,11是它的后驱;对于12而言,11是它的前继。
前继:
TreeNode treePredecessor(x){
// 11 -> 10
if(x.left != null)
return treeMaxium(x.left);
// 12 -> 11
y = x.p;
while(y!=null && x==y.left){
x = y;
y = y.p;
}
return y;
}
后驱:
TreeNode treeSuccessor(x){
// 11 -> 12
if (x.right != null)
return treeMinimum(x.right);
// 10 -> 11
y = x.p;
while (y!=null && x==y.right){
x = y;
y = y.p;
}
return y;
}
以上几个操作二叉搜索树与红黑树是相同的,这几个算是树的使用;下边的插入与删除,则不同,算是树的生成与调整。
插入
插入的过程是根据要插入的key,找到合适的位置,并且修改其父节点指向的过程。
void treeInsert(T, z){
y = null;
x = T.root;
while(x != null){
y = x;
if(z.key < x.key)
x = x.left;
else
x = x.right;
}
z.p = y;
// 更新父节点
if (y == null)
T.root = z; // 空树
else if (z.key < y.key)
y.left = z;
else
y.right = z
}
删除
删除是插入的逆运算,但比插入会复杂一些,因为删除时不光要考虑其自身与父节点,还要考虑其子节点。它分成3种情况:
- 如果z没有孩子节点,删除该节点,更新父节点
- 如果z只有1个孩子,那么将该孩子提升到z的位置,并修改z的父节点的相关指针指向z
- 如果z有2个孩子,那么可以先从找到z的后继(也可以是前驱)y,然后用y来替换z
// 用v替换u
void transplant(T, u, v){
if (u.p == null)
T.root = v;
else if (u ==u.p.left)
u.p.left = v;
else
u.p.right = v;
if (v != null)
v.p = u.p;
}
void treeDelete(T, z){
if (z.left == null)
transplant(T, z, z.right);
else if(z.right == null)
transplant(T, z, z.left);
else {
// 求后继y,用后继替换被删节点
y = treeMinimum(z.right);
if (y.p != z){
// 优化,移除y,并更新右侧
transplant(T, y, y.right);
y.right = z.right;
y.right.p = y;
}
// y 替换 z
transplant(T, z, y);
y.left = z.left;
y.left.p = y;
}
}
2. 红黑树原理
普通的二叉搜索树容易退化成链表,而红黑树是一种平衡的搜索树,它不会退化成链表。
红黑树在每个节点上增加一个存储位来表示节点的颜色,可以使RED或者BLACK。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,红黑树确保没有条路径比其他路径长出2倍,因而是近似于平衡的。
红黑树性质
- 节点是红色或者黑色
- 根节点是黑色
- 每个红节点必须有2个黑色的子节点
- 从任一节点到每个叶子节点的所有简单路径都包含 相同数目的黑色节点
红黑树降维
将红黑树所有的红节点与其父节点合并成一个节点
这个新形成的树称之为2-3-4树,因为它可能2个子节点、3个子节点或者4个子节点。
性质简化
这样红黑树的4条性质:
- 节点是红色或者黑色
- 根节点是黑色
- 每个红节点必须有2个黑色的子节点
- 从任一节点到每个叶子节点的所有简单路径都包含 相同数目的黑色节点
就简化成2-3-4树的2条性质:
- 节点只能是2节点、3节点、4节点之一,合并之后的元素最多有3个(4节点)
- 所有叶子节点的具有相同的深度,合并之后只剩黑节点,具有相同的深度。
相当于用空间属性替换了红黑的属性,降低了维度。
3. 红黑树操作
下边我们通过新变化的2-3-4树的操作反过来研究红黑树的操作,这里的操作指的是Insert与Delete2个操作。
插入
2-3-4树的插入的规则:
- 插入:从最下层参入;
- 升元:将插入结点由 2-结点升级成 3-结点,或由 3-结点升级成 4-结点;
- 递归升高:向 4-结点插入元素,先将中间元素提到父结点升元,原结点变成两个 2-结点,再把元素插入 2-结点中,如果父结点也是 4-结点,则递归向上层升元,至到根结点后将树高加1;
对应到红黑树里,就是:
- 新插入的结点颜色为
红色
,这样才可能不会对红黑树的高度产生影响。
- 2-结点对应红黑树中的单个黑色结点,插入时直接成功(对应 2-结点升元)。
- 3-结点对应红黑树中的
黑+红
子树,插入后将其修复成 红+黑+红
子树(对应 3-结点升元);
- 4-结点对应红黑树中的
红+黑+红
子树,插入后将其修复成红色祖父+黑色父叔+红色孩子
子树,然后再把祖父结点当成新插入的红色结点递归向上层修复,直至修复成功或遇到 root 结点;
这里将3->4 写了2个,虽然对于2-3-4树差别不大,但对于红黑树的实现还是有区别。11与12再加13时,只需要将13挂在12右子节点,然后左旋转12即可。对与11与13再加12时,需要先右旋一下12,然后再左旋一下12。
删除
对于二叉搜索树而言,删除是查询其后继,做了替换,在这里也是如此。
2-3-4树规则:
- 替换:查找离其最近的叶子节点(后继或前驱)替代被删除元素,然后从后继(或前驱)节点开始从下往上开始调整;
- 直接降元:4-结点变 3-结点,3-结点变 2-结点;
- 借元:2-结点中只有一个元素,删掉会造成树的深度不一致,所以下边会通过借点的方式来补充:
- 借兄弟结点中的元素来补充删除后的造成的空结点;
- 当兄弟结点中也没有多个元素可以补充时,尝试将父结点降元(兄弟与父亲借元的顺序可以颠倒);
- 当父节点失败时向上递归,至到子树降元成功或到 root 结点树高减1;
将这些规则对应到红黑树中即:
- 替换:查找后继(或前驱)节点来替换被删节点(如果被删是叶子节点,则不需要),从替代的叶子结点向上递归调整;
- 直接降元:替代结点颜色为红色(对应 2-3-4树中 4-结点或 3-结点)时删除子结点直接成功;
- 借元:替代结点为黑色(对应 2-3-4树中 2-结点)时,意味着替代结点所在的子树会降一层,需要依次检验以下三项,以恢复子树高度:
- 兄弟结点的子结点中有红色结点(兄弟结点对应 3-结点或 4-结点)能够“借用”,旋转过来后修正颜色;
- 父结点是红色结点(父结点对应 3-结点或 4-结点,可以降元)时,将父结点变黑色,自身和兄弟结点变红色后删除;
- 父结点和兄弟结点都是黑色时,将子树降一层后把
父结点当作替代结点
递归向上处理。
调整的过程如下图所示:
上图并没画出全部情况。最后递归借元,如下:
- 先合并父亲与兄弟节点
- 然后相当于删除父亲节点,从叔叔、祖父节点来充当父亲,依此递归
借鉴:通过2-3-4树理解红黑树
4. 具体实现
具体的实现参考:红黑树,这里仅摘抄部分代码
插入
void insert(Node *p, int data){
if(p->value >= data){
if(p->leftTree != NIL)
insert(p->leftTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->leftTree = tmp;
insert_case (tmp);
}
} else {
if(p->rightTree != NIL)
insert(p->rightTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->rightTree = tmp;
insert_case (tmp);
}
}
}
void insert_case(Node *p){
if(p->parent == NULL){
root = p;
p->color = BLACK;
return;
}
if(p->parent->color == RED){
if(p->uncle()->color == RED) {
p->parent->color = p->uncle()->color = BLACK;
p->grandparent()->color = RED;
insert_case(p->grandparent());
} else {
if(p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
rotate_left(p);
p->color = BLACK;
p->parent->color = RED;
rotate_right(p);
} else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
rotate_right(p);
p->color = BLACK;
p->parent->color = RED;
rotate_left(p);
} else if(p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_right(p->parent);
} else if(p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_left(p->parent);
}
}
}
}
删除
bool delete_child(Node *p, int data){
if(p->value > data){
if(p->leftTree == NIL){
return false;
}
return delete_child(p->leftTree, data);
} else if(p->value < data){
if(p->rightTree == NIL){
return false;
}
return delete_child(p->rightTree, data);
} else if(p->value == data){
if(p->rightTree == NIL){
delete_one_child (p);
return true;
}
Node *smallest = getSmallestChild(p->rightTree);
swap(p->value, smallest->value);
delete_one_child (smallest);
return true;
}else{
return false;
}
}
void delete_one_child(Node *p){
Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
if(p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL){
p = NULL;
root = p;
return;
}
if(p->parent == NULL){
delete p;
child->parent = NULL;
root = child;
root->color = BLACK;
return;
}
if(p->parent->leftTree == p){
p->parent->leftTree = child;
} else {
p->parent->rightTree = child;
}
child->parent = p->parent;
if(p->color == BLACK){
if(child->color == RED){
child->color = BLACK;
} else
delete_case (child);
}
delete p;
}
void delete_case(Node *p){
if(p->parent == NULL){
p->color = BLACK;
return;
}
if(p->sibling()->color == RED) {
p->parent->color = RED;
p->sibling()->color = BLACK;
if(p == p->parent->leftTree)
//rotate_left(p->sibling());
rotate_left(p->parent);
else
//rotate_right(p->sibling());
rotate_right(p->parent);
}
if(p->parent->color == BLACK && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
delete_case(p->parent);
} else if(p->parent->color == RED && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->parent->color = BLACK;
} else {
if(p->sibling()->color == BLACK) {
if(p == p->parent->leftTree && p->sibling()->leftTree->color == RED
&& p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling()->leftTree);
} else if(p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
&& p->sibling()->rightTree->color == RED) {
p->sibling()->color = RED;
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling()->rightTree);
}
}
p->sibling()->color = p->parent->color;
p->parent->color = BLACK;
if(p == p->parent->leftTree){
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling());
} else {
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling());
}
}
}