算法导论：第十三章.红黑树上之插入分析

一.何为红黑树？

红黑树是许多平衡(AVL)搜索树中的一种，它可以保证在最坏情况下基本动态集合的操作时间复杂度为O(lgn).

但既然它能被分支出来作为一颗单独的树学习，就一定有其特别之处，下面我们了解下一颗红黑树的基本特性：
1.节点内容有：color(颜色),key(信息),left(左孩子),right(右孩子),p(父母)

2.节点间的连接规则：（红黑树的性质）
（1）每个节点的color非黑即红
（2）根节点一定为黑色
（3）每个叶子节点一定为黑色
（4）若一个节点为红色则其孩子节点一定为黑色
（5）对于每个节点，从该节点到其所有后代节点的简单路径上一定包含相同数目的黑色节点
一颗典型的红黑树如下图所示：

由于它的性质我们需要知道：
1.从每个节点x出发（不含该节点）到达一个叶节点的任意一条简单路径上的黑色节点的个数称为该节点的黑高

二.为什么红黑树可以作为一种优秀的搜索树被使用？

我们知道一颗树的高度很大程度决定了一些操作的时间复杂度。高度越大，其时间复杂度越大，效率越低。
在红黑树中：一颗有n个内部节点的红黑树的高度最大为2lg(n+1).

因此动态集合的一系列操作均可在红黑树上O(lgn)时间内执行。

三.红黑树是如何实现一系列的操作的？

1.插入：
毋庸置疑，插入操作会打乱其性质，所以我们需要采取一定的措施还原它的性质。

但在此之前我们需要搞清楚：
如果我们需要向一颗红黑树插入一个元素的话我们一定会想到：插入后的节点颜色是设置为红色还是黑色呢？
如果设置为黑色，则一定会违反：（5）对于每个节点，从该节点到其所有后代节点的简单路径上一定包含相同数目的黑色节点

如果设置为红色，则可能违反：（4）若一个节点为红色则其孩子节点一定为黑色

所以相比之下，选择红色会更合理一点。

下面我们以一个例子正式开始分析红黑树的插入操作：
设插入节点为z

于是现在我们要学习如何变换颜色，如何旋转调节？
这个需要分情况讨论：

情况1：z的叔叔节点是红色的
z的父节点，叔叔节点，祖父节都变色。
z=z.p.p;

情况2：z的叔叔节点是黑色的且z是一个右孩子
z=z.p;
z向左旋转

情况3：z的叔叔节点是黑色的且z是一个左孩子
z.p.color=black;
z.p.p.color=red;
z.p.p向右旋转

流程图如下：

通过上面的调节我们可以在插入操作后还原红黑树。