红黑树介绍与分析

红黑树介绍与分析

最近觉得C++生疏了，拿出侯捷的《STL源码剖析》翻了翻，看到C++ set，map底层实现机制，其中采用的就是红黑树数据结构，另外Linux内核对内存管理和进程调度都用到了红黑树，看来它不能让人小视。自己从网上和书上重新看了下红黑树，把个人的理解放到博客上，跟大家讨论，也作为自己的重新梳理的方式。

红黑树(Red-Black Tree)

它是在1972 年由Rudolf Bayer 发明的，他称之为"对称二叉B 树"，它现代的名字是在Leo J. Guibas 和Robert Sedgewick 于1978 年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树本身是二叉搜索树，同时它应该始终满足五个性质：

红黑树每个节点颜色非红即黑；

根节点颜色必须为黑色；

每个叶节点(指的NULL指针节点)颜色均为黑；

不可以出现相邻的两个红色节点；

对于每个节点，其左右子树中的黑色节点个数必须相等；

一棵正常的红黑树如下图(引自wiki)：

红黑树的难点在于插入和删除操作涉及到的红黑树重新调整问题，关于原理性问题，有篇文章《红黑树原理详解》，作者：余强.  讲的比较清楚，也可以参照《CLRS》第13章红黑树的描述，以下主要结合c语言实现代码加注释的方式进行分析，编完代码后进行了一定的测试，如果还存在问题，可回帖反馈，我会进行更改，谢谢。

插入操作：

新插入一个节点时，其颜色未定，可以选择黑色也可以选择红色，但是仔细看下上述红黑树5个性质，会发现，插入黑色节点必然会导致性质5被破坏(空树除外)，而如果插入红色节点，则可能破坏性质4，这其中有一定的几率无需调整红黑树(父节点为黑色)，因此插入的新节点颜色设置为红色，以下插入操作均不考虑是空树和父节点是黑色的情况，因为这两种情况无需进行调整。

而如果发生上面说的破坏性质4，即新插入节点与父节点均是红色的情况，则我们需要将这两个相邻红色节点分开，以使性质4重新被满足，而涉及到的调整则需要看新插入节点的父节点、叔父节点以及祖父节点颜色而定，可以分情况讨论之；

首先考虑叔父节点的颜色，这里以叔父节点的颜色来划分接下来的调整操作是因为插入的新节点与其父节点均为红色，目的为了将这两个红色节点分开，可以通过性质推理知祖父节点必然为黑色，因为插入新节点前，树是满足性质的，而父节点颜色为红色，因此祖父节点必然为黑色。调整颜色过程中，如果需要改变父节点颜色，则必然需要考虑叔父节点，因此叔父节点是插入操作分情况讨论的关键点。

在介绍插入后红黑树重新调整前，首先引入左旋操作和右旋操作，在红黑树所有调整中，均采用左右旋操作解决节点移动问题，左右旋操作并不破坏二叉搜索树的性质，因此不会引入额外的重新对红黑树进行排序的负担，具体左右旋操作可参考其他红黑树相关文章或下文中对于左右旋操作的代码分析加注释；

重回正题，首先对插入操作所需要的调整进行分情况讨论，再次强调父节点为黑色的情况不分析，因为无需作过多调整，所以下面操作中父节点颜色均为红色：

叔父节点颜色为黑色：

以上两种情况为插入节点的父节点在祖父节点的左子树情况，当位于右子树时，情况类似。

以上两种情况，即新插入节点分别为外侧插入和内侧插入时，需要将父节点和新节点的相邻红色分开，该两种情况下叔父节点应该为NULL节点(如果有不正确，请大家指正

)

因此调整操作是以祖父节点为基点，父节点和祖父节点的连接为轴进行右旋转（内侧插入即第二种情况必须先以父节点为基点进行左旋调整），然后改变父节点和祖父节点的颜色。

新节点外侧插入情况：以祖父节点为基点，右单选，改变父节点和祖父节点颜色；

新节点内侧插入情况：先对父节点左单选（如果这里不进行左旋转，则经过下一步的右旋转后，新节点即成为祖父节点的左孩子，如果祖父节点为红色，则会引入额外的调整和麻烦），改变新节点和祖父节点颜色，再对祖父节点右单旋；

叔父节点颜色为红色

该情况下比较简单，因为叔父和父节点都是红色，而且祖父节点为黑色，则将祖父节点颜色变为红色，父节点和叔父节点颜色为黑色，即可消除相邻的两个红色节点而且不改变相应的黑高度，此时如果曾祖父节点颜色为黑色，则调整结束，如果曾祖父节点颜色为红色，则可将祖父节点视为新节点，递归新插入情况，迭代向上处理。

总体来说插入情况相对比较简单，主要涉及上述几种操作，以下是c语言相关红黑树插入实现代码：

/*

* key:新插入节点键值,root:红黑树根节点

* 红黑树节点插入

* 1、插入新节点

* 2、旋转红黑树并做颜色调整

*/

rb_node_t *rb_tree_insert(int key, rb_node_t* root)

{

rb_node_t *last_node;

rb_node_t *curnode;

/* 创建节点 */

rb_node_t *node = (rb_node_t *)malloc(sizeof(rb_node_t));

node->key = key;

curnode = root; //temp node,just for save something

/* 树为空 */

if (NULL == root)

{

node->color = black;

node->left_child = NULL;

node->right_child = NULL;

node->parent = NULL;

return node;

}

/* 向下搜索，直到找到相应的位置可以插入 */

while (curnode)

{

last_node = curnode;

node->key > curnode->key ? (curnode = curnode->right_child) : (curnode = curnode->left_child);

}

/* 判断插入搜索到的节点的左孩子还是右孩子 */

if (node->key > last_node->key)

last_node->right_child = node;

else

last_node->left_child = node;

node->parent = last_node;        //回马枪设置父节点

node->left_child = NULL;

node->right_child = NULL;

node->color = red;

/* 重新使红黑树调整为平衡状态 */

root = rb_tree_rebalance(node, root);

return root;

}

删除操作：

红黑树节点删除操作后的调整相比插入操作更加复杂，但是同样可以分情况讨论之。

首先红黑树删除同样采取跟二叉搜索树同样的删除方式，即如果需要删除节点A，则将A左子树中最大的节点(即最右边节点)和右子树中最小的节点(最左边的节点)删除，然后用删除节点替换A节点。

如下图：

需要删除8节点时，先搜索到7或9节点，将对应节点删除掉，同时将7或9的节点替换8的节点，详细参考请查阅二叉搜索树的删除。