红黑树演示
Red/Black Tree Demonstration: Maintenance Version
转自：http://peterpannju.blogbus.com/logs/21992610.html 红黑树是个复杂的数据结构。其插入，删除操作复杂度都为O(lgn)。
红黑树在 linux
内核中应用很多，比如虚拟内存管理，进程调度等。且其常常和 hash 一起出现，是非常重要的数据结构。
Contents:
Defination of Red-Black Tree
Insertion
Deletion
Comparison with BST & AVL
Red-Black Tree
Demonstration
Defination
of Red-Black Tree
As defined in CLRS, a red-black
tree is a binary search tree (BST) that
satisfies the following properties:
- Every node is either red or black.
- The root is
black. - Every leaf (NIL) is black.
- If a node is red, then
both its children are black. (Or in other
words, two red nodes may not be adjacent.) - For each node, all
paths from the node to descendant leaves
contain the same number of black nodes.
红黑树的数据并不存储在叶节点上。叶节点全部是 NIL。这可以帮助红黑树插入删除操作。
红黑树的高度不超过2lg(n+1)。证明请参考
CLRS。
Insertion
红黑树的插入方法有两种。分别为 Okasaki's Insertion Method 和 CLRS Insertion
Method。CLRS给出的方法比 Okasaki 的更复杂，但是效率较高。这里，我们采用 CLRS 中所采用的方法。
static void rb_insert_color(rb_node_t
* node, rb_root_t * root)
{
rb_node_t * parent, * gparent;
node->rb_color = RB_RED; //首先将 node
节点染成红色，这样可以 保证不增加 black height
while ((parent = node->rb_parent)
&& parent->rb_color == RB_RED) //当
父节点是红色时，违背条件 4，循环
{
gparent = parent->rb_parent;
//分两种情况：如果父节点是爷爷节点的左节点
if (parent == gparent->rb_left)
{
register rb_node_t * uncle =
gparent->rb_right;
//-->如果叔叔节点是红色，只需要修改颜色，不增加任一条支路
(gp->p->node/gp->u)的 black height，重新开始循环
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;
}
//-->如果叔叔节点是黑色，上面的方法就不行了，因为会增加
(gp->p->node)这条支路上的 black height，使树不平衡。
//所以，分为如下情况：
// 1. 如果node节点是父节点的右节点，则对 父节点左旋，转化为情况2
if (parent->rb_right == node)
{
register rb_node_t * tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
// 2. 如果node节点是父节点的左节点，则对 祖先节点右旋，注意染色
parent->rb_color = RB_BLACK;
gparent->rb_color = RB_RED;
__rb_rotate_right(gparent, root);
}
//另一种对称情况，此处省略
else {如果父节点是爷
爷节点的右节点的情况}
root->rb_node->rb_color = RB_BLACK;
}
Deletion
红黑树的删除操作比插入操作稍微复杂些，首先，我们需要用 BST-Delete(T, n)
删除节点。注意，此处删除的节点不一定就是n指向的节点，可能是其右子树中的最小节点(具体请参考 CLRS BST-Delete(T, x))。
然后，我们令被删除的节点(注意不一定为n)为x，其兄节点为w，分为如下四种情况：
Case1: w为红色。
Case2: w为黑色，w的两个孩子都是黑色。
Case3:
w为黑色，w的左孩子为红色，w的右孩子为黑色。
Case4: w为黑色，w的右孩子为红色。
转换图如下：
Case1 => Case2/Case3/Case4
Case2 => Case4
最后，我们将x染黑。
Comparison with BST & AVL
关于红黑树和 AVL & BST 的比较，有人叙述如下：
AVL trees are actually
easier to implement than RB trees because there
are fewer cases. And AVL trees require O(1) rotations on an insertion,
whereas red-black trees require O(lg n).
In practice, the speed of
AVL trees versus red-black trees will depend on the data that you're
inserting. If your data is well distributed,
so that an unbalanced
binary tree would generally be acceptable (i.e. roughly in random
order), but you want to handle bad cases
anyway, then red-black trees
will be faster because they do less unnecessary
rebalancing of already
acceptable data. On the other hand, if a
pathological insertion order
(e.g. increasing order of key) is common, then AVL trees will be
faster, because the stricter balancing rule will reduce the tree's
height.
Splay trees might be even faster than either RB or AVL
trees,depending on your data access distribution. And if you can use a
hash instead of a tree, then that'll be fastest of all.
红黑树，AVL树，BST都有自己的适用范围，不能一言以蔽之谁更好。
Splay Tree 我没有尝试过，以前学过的 《Java 数据结构》那本书上有相应的一节介绍。
Red-Black Tree Demonstration
这儿有红黑树用 JApplet
做的例子，给出了可视化的操作，很有意思。
http://gauss.ececs.uc.edu/RedBlackTester/redblack.html
参考文章：
一篇介绍红黑树的英文文献，其
中对 Okasaki's Insertion Method 有介绍，并且有红黑树高度不超过2lg(n+1)的证明。它给出的 Deletion
Method 和 CLRS中的(这篇文章中的)稍有不同，请跳转查看。
上面英文文献的中文版本，附
有 AVL 树的比较。但是笔者的翻译水平不怎么样。
内核中的红黑树实现，附有我对插入
操作写的部分注释。本文中的代码也是选自此处。
评论
发表评论