红黑树学习

红黑树的是一种特殊的二叉搜索树，有如下性质：

    性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3 每个叶节点是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

   性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

 

 

红黑树和AVL树的区别

在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时，已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。

关于红黑树是不是AVL的一种，我认为不是。如图构造一颗红黑树，但其显然不是平衡树，按《算法导论》的原话，它是接近平衡的。

红黑树的应用：

红黑树优异的性能在各个地方均可以大显身手。

STL标准模板库的set和map容器，底层均采用红黑树的机制来实现

Linux内核中内存的管理有两种方式，一个是链表，另外一种方式就是红黑树；具体来说，可以通过内存描述符中的mmap和mm_rb来访问内存区域。

红黑树插入的时候调整四种情况

http://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html?ca=drs-#author

一共分为四种情况：

（1）       新节点是红黑树的根节点；

在这种情形下，直接将它设置为黑色以满足性质 2

（2）       新节点的父节点是黑色的；

在这种情况下，新插入的节点是红色的，因此依然满足性质 4。而且因为新节点 N 有两个黑色叶子节点；但是由于新节点 N是红色，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足性质5。

（3）       父节点P和父节点的兄弟节点U都是红色

在这种情况下，程序应该将 P 节点、U 节点都设置为黑色，并将 P 节点的父节点设为红色（用来保持性质 5）。现在新节点 N 有了一个黑色的父节点 P。由于从 P 节点、U 节点到根节点的任何路径都必须通过 G 节点，在这些路径上的黑节点数目没有改变（原来有叶子和 G 节点两个黑色节点，现在有叶子和 P 两个黑色节点）。经过上面处理后，红色的 G 节点的父节点也有可能是红色的，这就违反了性质 4，因此还需要对 G 节点递归地进行整个过程（把 G 当成是新插入的节点进行处理即可）。

                                

（4）       父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是父节点 P 的右子节点，而父节点 P 又是其父节点 G 的左子节点。

在这种情形下，我们进行一次左旋转对新节点和其父节点进行，接着按情形 5 处理以前的父节点 P（也就是把 P 当成新插入的节点即可）。这导致某些路径通过它们以前不通过的新节点 N 或父节点 P 的其中之一，但是这两个节点都是红色的，因此不会影响性质 5。

                            

（5）       父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是其父节点的左子节点，而父节点 P 又是其父节点 G 的左子节点。

                                

这种情形下，需要对节点 G 的一次右旋转，在旋转产生的树中，以前的父节点 P 现在是新节点 N 和节点 G 的父节点。由于以前的节点 G 是黑色，否则父节点 P 就不可能是红色，我们切换以前的父节点 P 和节点 G 的颜色，使之满足性质 4，性质 5 也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是三个节点中唯一的黑色节点。

 

实际上，记住（3）和（5）就可以了。遇到（4）转换成（5）的情况即可。

由此观之，要理解红黑树，必须理解旋转的概念。

1.左旋

 

理解如下（看了1个小时，以前一直没有看懂，还是画图好些）：

1.rb_node_t* right = node ->right;

新建一个right指针来取得node->right的操作权；

如图所示：

 

 

 

 

 

 

2.node->right = right->left；

如图所示

 

3.right->left->parent = node;

 

b的parent指针指向了node。为了图片的简洁，我省略了画出parent指针

4.right->left = node;

  node节点成为了right节点的左孩子，如图所示：

 

5.node->parent->right = right or node->parent->left = right

处理node的父亲节点的指针，node父亲节点的孩子现在变成了right。

右旋的情况于此相类似，

如此，就基本实现了红黑树的插入操作。

红黑树的删除操作还没有看

 

左旋node节点如下：

|  node             right

|  /  /       ==>   /  /

|  a  right        node y

|     /  /             / /

|             b       y                               a      b

 

代码描述如下（摘自http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx）

 

 static rb_node_t* rb_rotate_left(rb_node_t* node,rb_node_t* root) { rb_node_t* right = node ->right; if ((node->right = right->left)) right->left->parent = node; right->left = node; if ((right->parent = node->parent)) { if (node == node->parent->right) node->parent->right = right; else node->parent->left = right; } else { root = right; } node->parent = right; return root; }