查找算法——2-3查找树、左倾红黑树

平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。
　　 对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材，也就是让h维持在O（log n）左右，完成上述工作就很省时间。能够一直维持好身材，不因新增删除而长歪的搜寻树，叫做平衡树（balanced search tree）。

一、2-3查找树

2-3查找树是一种能够在动态插入当中保持完美平衡的数据结构，完美平衡即树中的所有空链接到根节点的距离都是相同的。在一棵大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个。为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。

一颗2-3查找树或为一颗空树，或由以下结点组成：

1. 2-结点，含有一个键(及其对应的值)和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
2. 3-结点，含有两个键(及其对应的值)和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

 
　　注意:　至于4-结点，则以此类推是含有三个键(及其对应的值)和四条链接，四条链接代表了从小到大的四个范围，这四个范围用三个键切分开。
　　将指向一颗空树的链接称为空链接，一颗完美的2-3查找树中的所有空链接到根节点的距离应该是相同的。

1. 查找操作

将二叉查找树的查找算法更一般化些就得到了2-3树的查找算法。要判断一个键是否在树中，我们先将它的根节点中的键比较。如果它和其中任意一个相等的，查找命中；否则我们就根据比较的结果指向相应区间的链接，并且在其指向的子树中递归地继续查找。如果是个空链接则查找未命中。

2. 插入操作

2-3查找树与二叉查找树的区别就在于2-3树不会像像二叉查找树那样：在找到合适的位置之后将要插入的键值对直接创建为一个新结点，然后插入。而是为了保证平衡，将键值映射融合到现有的结点当中，根据融合的情况再进行操作。
　　对于插入过程，可能会存在查找命中和查找未命中两种情况。查找命中的就直接更新结点中对应键的值即可；查找未命中有结束于2-结点处和结束于3-结点处两种情况，也就对应于向这两个结点中插入新键。

对于查找未命中的也就是说真正要增加一对键值映射而言，其实就是一个不断进行 融合-分解-融合-分解-融合... 的过程中，分解完一定要进行融合(分解了根节点的除外)，所以什么时候停止关键在于融合之后是否还需要分解或者是否是分解了根节点，所以一般化过程更直观的可以说是这样：融合-(分解-融合)-(分解-融合)...。当查找未命中结束于2-结点处时，我们需要将键值映射融合到这个2-结点使之成为了3-结点，3-结点允许在2-3树当中存在的，所以不必进行分解。
　　当查找未命中结束于3-结点处时，如果我们将键值映射融合到其中就会变成一个4-结点，这在2-3树中是不允许的，所以要进行分解。将这个4-结点(小键、中键、大键)分解成两个2-子结点(小键和大键)和一个它们的根节点(中键)，但这样虽然不存在4-树了，但确增加了局部的高度，所以下一步是要将这个根节点的键值映射以及两个指向子节点的链接指向融合到之前的3-结点的父结点当中去。
　　如果这个父结点是一个2-结点，那么融合过后就显然不必再进行分解了，如果这个父结点也是一个3-结点，就要继续重复上面的过程，直到融合到一个2-结点或者将根节点也分解了(这个时候是整棵树的高度提升了而不是局部)为止。

ps:书上说的先将2-结点+要插入的键值映射融合成4-结点，再分解成两个2-结点和一个根节点，说是因为4-结点比较方便转换为两个2-结点和一个根节点，但实际上也可以将4-结点这一中介省去，直接2-结点+要插入的键值映射变换成两个2-结点和一个根节点。

向2-结点中插入

一次融合就完毕了：

向3-结点中插入

以上分别是融合-(分解-融合)、融合-(分解-融合)-(分解-融合)、和融合-(分解-融合)-分解(分解了根节点)

3. 删除操作

书上没有讲删除操作，可参考这里的2-3查找树的插入与删除

4. 局部变换与全局性质

将一个4-结点分解为2-3树可能有6种情况，是以有无父结点如有的话从哪一侧插入的来分类。插入算法的根本之一在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。

这些局部变换也不会影响树的全局有序性和平衡性：任意空链接到根节点的路径长度都是相等的。如下图所示

5. 总结

和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。

2-3 树在最坏的情况下仍有较好的性能。每个操作中处理每个节点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的节点，所以任何查找或者插入的成本都不会超过对数级别。

其缺点是，用这种直白的表示方法实现大多数操作并不方便，因为需要处理的情况实在太多。我们需要维护两种不同类型的节点，将查找的键和节点中的每个键进行比较，将链接和其他信息从一种数据类型转换到另一种数据类型等等。实现这些不仅需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。平衡一颗树的初衷是为了消除最坏的情况，但我们希望这种保障所需要的代码能越少越好。所以，通常使用如红黑二叉查找树等简单数据结构来表达并实现它。

二、左倾红黑查找树

左倾红黑二叉查找树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：红链接是用一个2-结点左链接另一个2-结点来表示一个3-结点，黑链接则是2-3树当中的普通链接。这种表达的好处在于我们无需修改就可以直接使用标准二叉查找树的get()方法，并且对于任意的2-3树我们只需要对结点进行转换就可以得到一颗对应的左倾红黑二叉查找树(这里书上写的是二叉查找树，看了英文原文及结合上下文应该指的是左倾红黑树)。

左倾红黑树的定义如下：

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

 
　　满足这样定义的左倾红黑树和2-3树是一一对应的，那么这样就能够两个算法结合起来：二叉查找树中的简单高效的查找算法和2-3树中高效的平衡插入算法。

1. 颜色表示

每个结点都只会有一条指向自己的链接(从它的父结点指向它)，我们将链接的颜色保存在表示结点的Node数据类型的布尔变量color中。那么该变量为true，黑色则为false。约定空链接为黑色。为了代码的清晰我们定义了两个常量RED和BLACK来设置和测试变量。我们用私有方法isRead()来测试一个结点和它们的父结点之间的链接的颜色。当我们提到一个结点的颜色时，我们指的是指向该结点的链接的颜色，反之亦然。颜色表示的代码实现如图所示：

private static final boolean RED   = true;
    private static final boolean BLACK = false;

    // BST helper node data type
    private class Node {
        private Key key;           // key
        private Value val;         // associated data
        private Node left, right;  // links to left and right subtrees
        private boolean color;     // color of parent link
        private int size;          // subtree count

        public Node(Key key, Value val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }
    
    private boolean isRed(Node x) {
    if (x == null) return false;
    return x.color == RED;
    }

2. 旋转

旋转的主要目的是为了解决操作中出现的红色右链接或者两条连续的红链接，在操作完成前这些情况都会被小心的旋转来修复。旋转分为左旋转和右旋转，其实直白点应该说成是向左旋转和向右旋转。旋转的代码如下所示，在写旋转代码的时候可以配合手画图片来写(不用less、greater这种，直接123表示就行，写完每一行指针指向相应的对象)

private Node rotateRight(Node h) {
        // assert (h != null) && isRed(h.left);
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    // make a right-leaning link lean to the left
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = x.left.color;
        x.left.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

3. 结束说明

在去看了维基百科和网上的相关资料后，发现书上讲的这种基于2-3树基础上的红黑树，实际上是左倾红黑树(mdzz,不说清楚简直是坑...)，而这种左倾红黑树实现起来有没有论文上说的那么简单是有争议的，也有人经多次测试发现原版红黑树总是更快的，实际上也正如下面链接里提到的，在LLRB被提出后，算法导论还有java8仍然用的是原版的RB，这就已经很说明问题了。可以参考
Left-leaning red-black trees are hard to implement
Why are Red-Black trees so popular?
"Left Leaning Red Black Trees Considered Harmful" - TRUE or FALSE?
所以本文就此结束，对应章节修改成了左倾红黑树而不是红黑树