《算法》--红黑树

1. 红黑树的介绍

红黑树背后的基本思想是用标准的二叉查找树（完全由2-节点构成）和一些额外的信息（替换3-节点）来表示2-3树，我们将树中的链接分为两种类型：红链接将两个2-节点连接起来构成一个3-节点，黑链接则是2-3树中的普通链接。确切的说，我们将3-节点表示为由一条左斜的红色链接相连的两个2-节点。这样的话，对于任意的2-3树，只要对节点进行转换，我们都可以立即派生出一棵对应的二叉查找树，也就红黑二叉树，简称红黑树。

2. 红黑树的定义

1. 红链接均为左链接
2. 没有任何一个结点同时和两条红链接相连
3. 该树是完全平衡的，即任意空链接到根节点的路径上的黑链接数量相同。
   无论我们选择用何种方式去定义它们，红黑树都既是二叉查找树，也是2-3树。那么我们就能够将这两种数据结构的优点结合起来：二叉查找树中高效简洁的查找方法和2-3树种高效的平衡插入算法。

3. 红黑树的旋转

假设我们有一条红色的右链接需要被转化为左链接，这个操作叫做左旋转，同样，将一个红色的左链接转化为右链接称为右旋转。
在插入新键时，我们可以通过旋转帮助我们保证2-3树和红黑树的一一对应关系，因为旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性，也就是说，我们在红黑树中进行旋转时无需为树的有序性或者完美平衡性担心。下面我们来看看应该如何使用旋转操作来保持红黑树的另外两个重要性质：不存在两条连续的红链接和不存在红色的右链接。

4. 红黑树的插入

（1）向2-节点中插入新键

如果新键小于老键，我们只需要新增一个红色的结点即可。新的红黑树和单个的3-结点完全等价。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接。此时，我们需要将其旋转为红色的左链接。

（2）向一棵双键树（即一个3-结点）中插入新键

这种情况可分为3种子情况：
新键小于树中的两个键
它被连接到3-结点的右结点。此时树是平衡的，跟结点为中间大小的键，它有两条红链接分别和较大和较小的键相连。
在两者之间
它会被连接到最左边的空链接，这样就产生了两条连续的红链接，此时我们只需要将上层的红链接右旋转即可得到第一种情况。
大于树中的两个键
这种情况又会产生两条连续的红链接，一条红色左链接接一条红色右链接。此时我们只需要将下层的红链接左旋转，即可得到第二种情况，然后根据第二种情况的方法即可得到第一种情况的结果。

（3）向树底部的3-结点插入新键


在沿着插入点到根节点的路径向上移动时所经过的每个结点中顺序完成以下操作，我们就能完成插入操作：
如果右子结点是红色的而左子节点是黑色的，进行左旋转。
如果左子节点是红色的且它的左子节点也是红色的，进行右旋转。
如果左右子节点均为红色，进行颜色转换。

5. 红黑树的性质

1. 一棵大小为N的红黑树的高度不会超过2lgN.
2. 一棵大小为N的红黑树中，根节点到任意子节点的平均长度为lgN
3. 红黑树可以保证对数级别的查找和插入