【原创】Linux 系统之平衡树（红黑树）
0赞
发表于 5/21/2015 5:10:59 PM
阅读（2968）
之所以称为红黑树的原因就在于它的每个节点都被着色为红色或黑色。这些节点颜色被用来检测树的平衡性。但需要注意的是，红黑树并不是严格意义上的平衡二叉树，恰恰相反，红黑树放松了平衡二叉树的某些要求，由于一定限度的不平衡，红黑树的性能得到了提升。
从根节点到叶节点的黑色节点数被称为树的黑色高度（black-height）。前面关于红黑树的性质保证了从根节点到叶节点的路径长度不会超过任何其他路径的两倍。因此，对于给定的黑色高度为n的红黑树，从根到叶节点的简单路径的最短长度为n−1，最大长度为2×(n−1)。
红黑树在插入和删除操作中，节点可能需要被旋转以保持树的平衡。红黑树的平均和最差搜索时间都是O(log2N)。在实际应用中，红黑树的统计性能要好于严格平衡二叉树（如AVL树），但极端性能略差。
红黑树的定义
红黑树是指满足下列条件的二叉搜索树。
性质1：每个节点要么是红色，要么是黑色（后面将说明）。
性质2：所有的叶节点都是空节点，并且是黑色的。
性质3：如果一个节点是红色的，那么它的两个子节点都是黑色的。
性质4：节点到其子孙节点的每条简单路径都包含相同数目的黑色节点。
性质5：根节点永远是黑色的。
红黑树节点的插入过程
插入节点的过程如下。
在树中搜索插入点。
新节点将替代某个已经存在的空节点，并且将拥有两个作为子节点的空节点。
新节点标记为红色，其父节点的颜色根据红黑树的定义确定，如果需要，对树作调整。
存在两种情况
：
（1）情形1：红色父节点的兄弟节点也是红色的
？
（2）情形2：红色父节点的兄弟节点是黑色的？
红黑树节点的结束插入过程
插入结点时，可能会需要重新着色，或者旋转，来保持红黑树的性质。如果旋转完成，那么算法就结束了。对于重新着色来说，读者需要在子树的根节点留下一个红色节点，于是需要继续向上对树进行修整，以保持红黑树的性质。最坏情况下，用户将不得不对到树根的所有路径进行处理。
首先，以下是红黑树的定义，其位于<include/linux/rbtree.h>中。
struct
rb_node
{
struct
rb_node *rb_parent;
int
rb_color;
#define RB_RED 0
#define RB_BLACK 1
struct
rb_node
*rb_right;
struct
rb_node
*rb_left;
};
红黑树的颜色插入函数
void
rb_insert_color(struct
rb_node
*node, struct
rb_root
*root)
{
struct rb_node *parent, *gparent;
/*检查父节点的颜色是否为红色*/
while ((parent = node->rb_parent)
&& parent->rb_color
== RB_RED)
{
gparent
= parent->rb_parent;
/*判断父节点是否是祖父节点的左节点*/
if (parent == gparent->rb_left)
{
{
register struct
rb_node
*uncle = gparent->rb_right;
/*判断uncle节点是否为红色，并相应调整颜色*/
if (uncle && uncle->rb_color
== RB_RED)
{
uncle->rb_color
= RB_BLACK;
parent->rb_color
= RB_BLACK;
gparent->rb_color
= RB_RED;
node = gparent;
continue;
}
}
if (parent->rb_right
== node)
{
register struct
rb_node
*tmp;
/*左旋*/
__rb_rotate_left(parent,
root);
tmp = parent;
parent = node;
node = tmp;
}
parent->rb_color
= RB_BLACK;
gparent->rb_color
= RB_RED;
__rb_rotate_right(gparent,
root);
}
else { /*else部分与前面对称*/
{ register
struct
rb_node
*uncle = gparent->rb_left;
if (uncle && uncle->rb_color
== RB_RED)
{
uncle->rb_color
= RB_BLACK;
parent->rb_color
= RB_BLACK;
gparent->rb_color
= RB_RED;
node = gparent;
continue;
}
if (parent->rb_right
== node)
{
register struct
rb_node
*tmp;
/*左旋*/
__rb_rotate_left(parent,
root);
tmp = parent;
parent = node;
node = tmp;
}
parent->rb_color
= RB_BLACK;
gparent->rb_color
= RB_RED;
__rb_rotate_right(gparent,
root);
}
else { /*else部分与前面对称*/
{ register
struct
rb_node
*uncle = gparent->rb_left;
if (uncle && uncle->rb_color
== RB_RED)
{
uncle->rb_color
= RB_BLACK;
parent->rb_color
= RB_BLACK;
gparent->rb_color
= RB_RED;
node = gparent;
continue;
}
最近在给一个班讲基础，遇到了很多好玩的东西，与大家一起共勉。
