平衡查找树

1.1 2-3查找树

一棵2-3查找树或为一个空树，或由以下节点组成：

2-节点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向2-3树中的键都大于该节点。

3-节点，含有两个键（及其对应的值）和三条链接，左链接指向2-3树中的键都小于该节点，中链接指向的键都在两键之间，右链接指向的键都大于该节点。

一棵完美平衡的二叉查找树中的所有空链接到该节点的距离都应该是相同的。

1.1.1 查找

与二叉树类似。

1.1.2 向2-节点中插入

先进行一次未命中的查找，如果未命中的查找结束于2-节点，只要把它变成一个3-节点，将插入的键保存其中即可。如果结束与一个3-节点，则比较复杂，下面再讨论。

1.1.3 向仅有3-节点中插入

如上所述，它最后走到一个3-节点。这个节点中有两个键，所以在此节点中已经没有可插入新建的空间了。为了将新建插入，先临时将新键存入该节点中，使之成为一个4-节点。它很自然地扩展了以前的节点并含有3个键和4条链接。而且很容易地转换成由3个2-节点组成的2-3树，其中一个点（根）含有中键，一个节点含有3个键中的最小者（与根节点的左链接相连），一个节点含有3个键中的最大者（与跟节点的右链接相连）。这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美平衡的二叉树，因为其中所有的空链接到根节点的距离都相等。插入前树的高端为0，插入后的树的高度为1。这个例子说明了2-3树是如何生长的。

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

这种情况需要在维持树的完美平衡的前提下为新键腾出空间。像上面一样构造一个临时4-节点并把它分解，但此时不会为中键创建一个新节点，而是移动到原来的父节点。可以将这次转换看成原3-节点的一条链接替换为新父节点中的原中键左右两边的两条链接，并分别指向两个新的2-节点。而此情况中，父节点是有空间的。这次转换也不影响2-3树的主要性质完美平衡。这个转换是2-3树动态变化的核心。

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

此情况和上面的类似，只是当父节点为3-节点时，就一直向上递推，直到遇到一个2-节点或到达根。

在一棵大小为N的2-3树中，查找和插入访问的节点必然不超过logN个。

1.2 红黑树

1.2.1 替换3-结点

红黑树的基本思想是用基本二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。将树中的链接分为两类，红链接将两个2-结点连起来构成一个3-结点，黑链接则是2-3树中的普通链接。这种表示法的一个优点是，无须修改就可以直接使用标准二叉查找树的get方法。将这种方式表示2-3树的二叉查找树称为红黑树。

1.2.2 定义

红黑树是一种二叉查找树：

红链接均为左链接。

没有任何一个节点同时和两条红链接相连。

是完美黑色平衡的，即任意空链接到根节点的黑链接树相等。

1.2.3 一一对应

如果把红链接相连的结点合并，得到的就是一棵2-3树。相反，如果将一棵2-3树中的3-节点化作由红色左链接相连的两个2-结点，那么不会存在能够和两条红链接相连的节点，且树必然是完美黑色平衡的，因为黑链接即2-3树中的普通链接，根据定义这些链接必然是完美平衡的。无论完美怎么定义，红黑树既是二叉查找树，也是2-3树。因此可以将两个算法的优点结合起来，二叉查找树中简洁高效的查找方法和2-3树中平衡高效的插入算法。

1.2.4 颜色表示

当提到一个节点的颜色时，指的是指向该节点的颜色，反之亦然。实现代码如下：

1.2.5 旋转

1.2.6 向2-节点中插入新键

如果新键小于老键，只需要增加一个红色节点即可，新的红黑树与单个3-节点完全等价。如果新键大于老键，那么新增的红色节点将会产生一条红色的右链接。需要使用root = rotateLeft(root)来将其旋转为红色左链接并修正根节点的链接，插入操作才说完成。

1.2.7 向3-节点中插入新键

这种情况又能分为3种子情况：新键小于树中的两个键，在两者之间，或是大于树中的两个键。

1.2.8 颜色转换

如果一个节点连接了两个红色子节点，除了将子节点的颜色由红变黑之外，同时还要将父节点的颜色由黑变红。这个操作最重要的性质和旋转操作一样是局部变换，不会影响整棵树的黑色平衡性。

1.2.9 根节点总是黑色

由上可知，颜色转换可能使根节点变为红色。这说明根结点是3-节点的一部分（是某个节点的左子树），这显然是不可能的。因此我们在每次插入后都会将根节点设为黑色。注意，每当根节点由红变黑时树的根链接高度就会加1.

1.2.10 将红链接在树上向上传递

红黑树在实现插入时的关键步骤：要在一个三节点下插入新键，先创建一个临时的4-节点，将其分解并将红链接由中间键传递给它的父节点。重复这个过程，直到遇到一个2-节点或者根节点。

1.3 实现

1.4 删除

1.4.1 自顶而下的2-3-4树

2-3-4树中允许存在4-节点。它的插入算法沿查找路径向下进行变换是为了保证当前结点不是4-节点（这样树底才有空间来插入新的键），沿查找路径向上进行变换是为了将之前创建的4-节点配平。

1.4.2 删除最小键

2-3树删除最小键，从树底部的3-节点中删除键是很简单的，但2-节点则不然，会留下一个空节点，这样会破坏树的完美平衡性。为了保证不会删除一个2-节点，要沿着左链接向下进行变换，确保当前节点不是2-节点。

1.5 红黑树的性质

所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别（范围查找除外，它所需的额外时间）。

1.5.1 性能分析

一棵大小为N的红黑树的高度不会超过2logN。

一棵大小为N的红黑树中，根节点到任意节点的平均路径长度为~1.00logN。