数据结构

平衡查找树

在一棵含有N个结点的树中，我们希望树高为lgN，这样就能保证所有查找都能在lgN次比较内结束。但是在动态插入中保证树的完美平衡的代价太高，因此我们将稍微放松完美平衡的要求，学习一种保证所有操作（范围查找除外）均能够在对数时间内完成的数据结构。

2-3查找树

一棵2-3查找树或为一棵空树，或由2-结点、3-结点组成。一棵完美平衡的2-3查找树中的所有空链接到根节点的距离都应该是相同的。如下：

1、查找

要判断一个键是否在树中，先将它和根节点中的键比较，若相等则命中；否则根据比较结果找到指向相应的区间链接，递归查找。如果是空链接，则查找未命中。

2、向2-节点中插入新键

向树中插入新结点同时需要保证树的平衡性，我们可以先进行一次未命中的查找，如果结束于2-节点，则只要把这个2-结点替换为一个3-结点即可。同时也保证了树的平衡性。

3、向一棵只含有一个3-节点的树中插入新键

因为只含有一个3-结点，所以可以先把其变为临时的4-结点，然后分解为含有三个节点的树。

4、向一个父节点为2-节点的3-节点中插入新键

同理先将3-节点变成临时的4-节点，然后进行分解，将父节点变为3-节点。

5、向一个父节点为3-节点的3-节点中插入新键

现在假未命中的查找结束于一个父结点为3- 结点的结点。我们再次和刚才一样构造一个临时的4- 结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3- 结点，因此我们再用这个中键构造一个新的临时4- 结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。

6、分解根节点

若最终根节点变成了一个临时4-节点，就按照向一棵只含有一个3-节点的树中插入新键的方式分解根节点。

2-3树维持平衡的原理

将一个4-节点分解为一棵2-3树可能有如下6中情况，2-3树插入算法的根本在于这些变换是局部的，不会影响树的全局有序性和平衡性：任意空链接到根节点的路径长度相同。

如果在变换之前根节点到所有空链接的路径长度是h，那么变换之后长度仍然为h。只有当根节点被分解时，所有空链接到根节点的路径长度才会加1。

在一般的二叉查找树中，按照升序插入10个键会得到高度为9的一棵二叉查找树。但是使用2-3树，树高度为2。可以确定2-3树在最坏情况下仍然有较好的性能，任何查找或者插入的成本都不会超过对数级别。但缺点就是太难实现并且维护产生的额外开销可能会使算法比标准的二叉查找树更慢。

红黑二叉查找树

红黑二叉查找树基本思想是用标准的二叉查找树和一些额外的信息(替换3-结点)来表示2-3树。

红黑树定义

将树中的链接分为两种类型：红链接：将两个2-结点连接起来构成一个3-结点，黑链接：则是2-3树中的普通链接。即将3-结点转换为了2-结点和一个特殊的红链接。这样的优点就是可以直接使用标准二叉查找树的get()方法，将这种表示2-3树的二叉查找树称为红黑树。

另一种等价定义如下：

• 红链接均为左链接；
• 没有任何一个结点同时和两条红链接相连；
• 该树是完美黑色平衡的，即任意空链接到根节点的路径上黑链接数量相同。

满足这样定义的红黑树和相应的2-3树是一一对应的。因此红黑树能够将二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法结合起来。

颜色表示

我们将链接的颜色保存在表示节点的Node数据结构的布尔变量color中。红色定义为true，黑色定义为false。约定空链为黑色。

旋转

在实现某些操作中可能会出现红色右链接或者两条连续的红链接，此时需要旋转操作对其进行修复。

旋转操作可以保持红黑树的有序性和完美平衡性，下面介绍旋转操作如何保证红黑树另外两个重要性质：不存在两条连续的红链接和不存在红色的右链接。

向单个2-节点中插入新键

此操作分为向左插入还是向右插入，如下图示：

向树底部的2-节点插入新键

向一棵红黑树中插入一个新键会在树的底部新增一个节点，并且总是用红链将新节点与父节点相连，如果指向新结点是父节点的左链接，直接成为一个3-节点，否则进行旋转修复。

向一棵双键树(即一个3-结点)中插入新键

有三种情况：新键小于树中的两个键，在两者之间，或是大于树中的两个键。每种情况中都会产生一个同时连接到两条红链接的结点，我们的目标就是修正这一点。

向树底部的3-节点插入新键

• 颜色转换

专门用一个方法flipColors()来转换一个节点的两个红色子节点的颜色。除了将子节点的颜色由红变黑之外，还同时将父节点的颜色由黑变红。此操作的最重要性质依然是局部变换不会影响整棵树的黑色平衡性。

颜色转换会使根节点变为红色，红色的根节点说明根节点是一个3-结点的一部分，但实际上并不是这样。因此在每次插入后都会将根节点设为黑色。注意：每次根节点由红变黑时树的黑链接高度会加1。

要在一个3-结点下插入新键，先创建一个临时的4-结点，将其分解并将红链接由中间键传递给它的父节点，重复这个过程，就能将红链在树中向上传递，直到遇到一个2-结点或者根节点。