By: 潘云登
Date: 2009-7-21
Email: intrepyd@gmail.com
Homepage: http://blog.csdn.net/intrepyd
Copyright: 该文章版权由潘云登所有。可在非商业目的下任意传播和复制。
对于商业目的下对本文的任何行为需经作者同意。
1. 本文内容对应《算法导论》(第2版)》第13章。
2. 主要介绍了使二叉查找树保持平衡的红黑树，以及保持红黑树性质的旋转、插入和删除操作。其中，插入和删除操作较为复杂，画图分析每一种情况将有助于理解。
3. 希望本文对您有所帮助，也欢迎您给我提意见和建议。
4. 本文包含以下内容：
² 红黑树的性质
² 旋转操作
² 插入操作
² 删除操作
当二叉查找树出现不平衡，树的高度较高时，二叉查找树所支持的动态集合操作的性能可能不比用链表好。红黑树（red-black tree）是许多平衡的查找树中的一种。它保持二叉查找树性质，同时在每个结点上增加一个存储位表示结点的颜色。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因而是接近平衡的。可以证明，一棵有n个结点的红黑树的高度至多为2 lg(n+1)。
一棵二叉查找树如果满足下面的红黑性质，则为一棵红黑树：1）每个结点或是红的，或是黑的；2）根结点是黑的；3）每个叶结点（NULL）是黑的；4）如果一个结点是红的，则它的两个儿子都是黑的；5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。这种黑结点的个数称为该结点的黑高度bh。
这里，叶结点（NULL）实际上是之前介绍的树结构的叶结点的子结点，该子结点指针通常赋值为NULL。为了方便处理边界条件，可以采用一个哨兵nil统一表示此类NULL结点，包括树根结点的父结点。哨兵nil的颜色为黑色。
|
typedef struct node { int key; int color; struct node *left; struct node *right; struct node *parent; } rbt_node; |
红黑树的查询操作与二叉查找树相同，如关键字查询、最大关键字结点、最小关键字结点、前趋结点和后继结点等。但是，二叉查找树的插入和删除操作可能破坏红黑树性质。为保持红黑树性质，就要改变树中某些结点的颜色及指针结构。指针结构的修改是通过旋转操作来完成的。旋转操作是一种能保持二叉查找树性质的查找树局部操作，分为左旋和右旋。当在某个结点x上做左旋操作时，x为子树的根，假设它的右子结点y不是nil。在左旋之后，y成为子树新的根，x成为y的左子结点，而y的左子结点成为x的右子结点。可以看到，左旋是以某个结点到其右子结点之间的链为支轴进行。
|
void left_rotate(rbt_node **root, rbt_node *x_node) { rbt_node *y_node=&nil;
y_node = x_node->right; x_node->right = y_node->left; /*将y的左子树作为x的右子树*/ if(y_node->left != &nil) y_node->left->parent = x_node; y_node->parent = x_node->parent; /*链接x的父结点和y*/ if(x_node->parent == &nil) *root = y_node; else if(x_node == x_node->parent->left) x_node->parent->left = y_node; else x_node->parent->right = y_node; y_node->left = x_node; /*使x成为y的左子结点*/ x_node->parent = y_node; } |
右旋与左旋类似。它以某个结点到其左子结点之间的链为支轴进行。当在某个结点x上做右旋操作时，x为子树的根，假设它的左子结点y不是nil。在右旋之后，y成为子树新的根，x成为y的右子结点，而y的右子结点成为x的左子结点。
|
void right_rotate(rbt_node **root, rbt_node *x_node) { rbt_node *y_node=&nil;
y_node = x_node->left; x_node->left = y_node->right; /*将y的右子树作为x的左子树*/ if(y_node->right != &nil) y_node->right->parent = x_node; y_node->parent = x_node->parent; /*链接x的父结点和y*/ if(x_node->parent == &nil) *root = y_node; else if(x_node == x_node->parent->left) x_node->parent->left = y_node; else x_node->parent->right = y_node; y_node->right = x_node; /*使x成为y的右子结点*/ x_node->parent = y_node; } |
红黑树的插入操作以二叉查找树的插入操作为基础，加上一个辅助过程，用以对结点进行重新着色并旋转，从而保持红黑树性质。首先，新插入的结点z总是被着上红色。插入操作只可能破坏红黑树的性质2）或性质4），并且只会有一个性质被破坏。如果违反性质2），则发生的原因是z是根而且是红的。如果违反性质4），则原因是z和z.parent都是红的。第一种情形，只要将z重新着上黑色。第二种情形，需要分六种情况讨论。前三种与后三种相互对称，区别在于z的父结点是其祖父结点的左子结点还是右子结点。情况1）与情况2）3）的区别在于z的父结点的兄弟结点（叔叔）的颜色有所不同。所有三种情况中，z的祖父结点总是黑的，这由性质4）保证，因为z的父结点是红的。
情况1）z的叔叔y为右子结点，是红的。这时，z为当前节点，z的父结点z.parent和叔叔y都是红的，z的祖父是黑的。可以将z的父亲和叔叔都着上黑色以解决z和z.parent都是红色的问题，将z的祖父着上红色以保持性质5）。然后，把z的祖父当作当前结点，再次检查z的父结点是否为红的。换句话说，上述循环的终止条件是z的父结点为黑色。这时，z为红色，如果z的父亲为nil（黑色），即z为树根，性质2）被违反，只要将z着上黑色便可加以修正。新插入结点为树根的情况与此相同。
情况2）z的叔叔y为右子结点，是黑的，而且z是右子结点。将z设为z的父结点（z上升一层），然后对z做一次左旋操作（z下降一层），将情况2）转变为情况3）。这时，仍然只有性质4）被破坏。由于z的层数不变，z的祖父的身份保持不变。
情况3）z的叔叔y为右子结点，是黑的，而且z是左子结点。这时，z的左右子树、z的父亲的右子树，以及z的祖父的右子树（以z的叔叔为子树的根），它们的黑高度相同，性质5）成立，只有性质4）在z和z的父结点之间被破坏。通过将z的父亲着成黑色，将z的祖父着成红色，并且对z的祖父执行一次右旋操作，可以修正性质4）。所有红黑树性质得以保持，循环终止条件（z的父结点为黑的）成立。由于z原先的祖父现在成为z父结点的右子结点，树的高度减小1，这正是红黑树保持平衡的关键所在。
情况4）z的叔叔y为左子结点，是红的。与情况1）相同，将z的父亲和叔叔都着上黑色以解决z和z.parent都是红色的问题，将z的祖父着上红色以保持性质5）。然后，把z的祖父当作当前结点，再次检查z的父结点是否为红的。
情况5）z的叔叔y