Red-Black-BST

基于二叉查找树的查找和插入算法已经可以应用在许多的用例特定的应用程序上，但是在最坏的情况下，其结构退化为链表的性能急剧降低。这是让人无法容忍的。

由于二叉查找树的查询性能依赖于树的形态，如果可以找到一种方法可以让二叉查找树无论如何构造，都可以处于一个平衡的状态。我们就可以在更多的情况下应用二叉查找树的高效查找和插入等操作。

在理想情况下我们希望二叉查找树能在每次插入，删除等操作后都保持一个完美的平衡状态。在一颗含有 N 个结点的二叉查找树中，树高为 lgN 。这样就可以保证在 lgN 次比较内查询到元素，达到二分查找的性能。

但是实际情况是，在动态的插入和删除等操作中保持二叉查找树的完美平衡的代价太高了，我们需要降低要求，让二叉查找树保持一个接近于完美平衡的状态。这就是红黑二叉查找树。

1. 2-3查找树

学习红黑二叉查找树之前，我们需要先了解2-3查找树，它可以让我们更好的了解红黑二叉查找树保持树平衡的原理。 在一般情况下，我们将一颗标准二叉查找树上的结点称为：2-结点（含有一个键和两条链接）。为了保持树的平衡性，在一颗2-3查找树中还含有： 3-结点（含有两个键三条链接）,左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树中的键都位于该结点的两个键之间，右链接指向的 2-3树中的键都大于该结点。 下图所示就是一颗2-3查找树。

了解2-3查找树的基本结构后，我们进一步学习分析2-3查找树如何完成二叉查找树的各项功能，以及其保持树的完美平衡的方法。

1.1 查找

2-3查找树的查找算法与二叉查找树基本类似，只是2-3树会多一些判断，只要将二叉查找树的查找算法一般化我们就可以得到2-3查找树的算法。判断一个键是否在2-3查找树中的基本流程为：

1. 将查找键与根结点中的键比较，如果它与其中任意一个是等，查找命中。
2. 若未命中，根据比较结果确定查找键对应的区间，根据区间的链接找到子树继续递归的查找。
3. 如果链接最后为空链接，则查询未命中。

1.2 向2-结点插入新键

在二叉查找树中，进行一个插入操作首先会进行一次未命中查找。然后将新结点插入到树的底部，这样就有可能破坏树的平衡性。而在一颗2-3查找树中，如果查找未命中结束于一个2-结点。我们只需要将2-结点替换为3-结点。将需要插入的键保存在其中即可，如下图所示。

1.3 向3-结点插入新键

向3-结点中插入新键就比向2-结点中插入新键要更复杂一些，因为3-结点已经含有了两个键没有插入空间了。但是为了将新键插入，我们可以键该键临时的存入该结点中,该结点就成为了一个4-结点（含有3个键4条链接）。由于4-结点是临时的，我们必须将它分解变换成2-结点或3-结点，一颗4-结点很容易转换成一颗由3个2-结点构成的2-3查找树。原4-结点中的中间结点成为此树的根节点。这颗树既是一个3个结点的二叉树，也是一颗完美平衡的2-3树。转换的过程揭示了一颗2-3树是如何 “生长” 的。具体如下图所示。

1.4 向一个父结点是2-结点的3-结点中插入新键

假设一次插入的未命中查找操作结束于一个3-结点，且它的父结点是一颗2-结点。在这种情况下我们需要保持树的完美平衡的前提下，将新键插入。我们可以像在1.3节中描述的一样，将3-结点临时的转换为一个4-结点，但是此时我们不能直接将4-结点分解为2-结点，因为此操作会破坏2-3树的完美平衡。我们将4-结点的中键上移存入原来父结点中。其他两个键分解为2个2-结点，连接在父结点原中键两端的链接上。由于原来的父结点是2-结点有插入空间，可以直接将中键插入到此结点中。经过此操作2-3树任是完美平衡的，所有的空链接到根结点的距离仍然相等，具体过程如下图所示。

1.5 向一个父结点是3-结点的3-结点中插入新键

假设一次插入的未命中查询操作结束于一个父结点为3-结点的3结点中。和1.4一样我们先构造一个临时的4-结点，然后将它的中键移动到父结点中。但是父结点也是一个3-结点，因此我们需要再次构建一个临时4-结点，然后进行相同的变换，分解结点并将中键移动到父结点中。如果路径上的结点除开根结点全部都是3-结点，我们就需要一直重复构建和分解临时的4-结点，将中键插入更高层的父结点中。直到最后达到根结点。具体过程如下图所示。

1.6 分解根结点

如果从插入结点到到根节点全部都是3-结点，在经历数次变换后根结点最后会变换成一个临时的4-结点。此时我们就可以直接将4-结点直接分解为3个2-结点，它的中键变成新的根节点，左右两个键连接在新的根结点的左右链接上。操作完成后树高加1，如下图所示。显而易见此次变换的仍保持了2-3树的完美平衡性。

1.7 全局性质

将一个 4- 结点分解为一棵 2-3 树可能有 6 种情况，都总结在了图 3.3.8 中。这个 4- 结点可能是根结点，可能是一个 2- 结点的左子结点或者右子结点，也可能是一个 3- 结点的左子结点、中子结点或者右子结点。 2-3 树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。每个变换都会将 4- 结点中的一个键送入它的父结点中，并重构相应的链接而不必涉及树的其他部分。

这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。因为在所有非根结点的上的操作都在保持树完美平衡性的情况下 良好的保持了2-3查找树的有序性。只有在根结点需要转换为一个临时4-结点并分解为3个2-结点时才会使树高加1。

1.8 测试

根据上述2-3查找树的原理，我们就可以模拟插入，根据最后生成树的形态判断树的性能。使用两组用例进行测试，一组是键按随机的顺序插入，二组是按键值的正序插入，测试过程和结果如下图所示。

根据最后的插入结果，我们可以确定的是2-3查找树在最坏的插入情况下仍具有良好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。

可惜的是，虽然2-3树在逻辑上很好的解决了查找树平衡的问题，但是这种直白的表示方法实现大多数操作并不方便，因为需要处理的情况实在太多。需要维护几种不同类型的结点，将被查找的键与结点中的每一个键比较，将链接等信息从一个结点复制到另外一个结点，将结点从一种数据类型转换到另一种数据类型。实现这些操作不仅需要大量的代码，而且它们的所产生的额外开销可能会使算法比标准的二叉查找树更慢。平衡一颗查找树的初衷是为了消除最坏插入情况带来的影响，但我们想要这种维持查找树平衡的方法所需要的开销以及代码能够越少越好。

2.红黑二叉查找树

上文中2-3树插入算法的逻辑思路是非常清晰易于理解的，但是 直接 实现的额外开销以及代码量都较大。而红黑二叉查找树可以在逻辑上表达实现它，且实现的代码量以及额开销都很小。红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外信息（替换3-结点）来表示2-3查找树。

2.1 替换3-结点

在红黑二叉查找树中，结点的链接分为两种类型：红链接将两个2-结点连接起来构成一个2-3树中的3-结点，黑链接则是2-3树的普通链接。准确的说，在红黑二叉查找树中用一条左斜的红色链接相连的2个结点来表示2-3树中的3-结点。根据红黑二叉树的定义原理，很多对二叉查找树的操作可以直接拿来使用。而且其他操作和标准的二叉查找树的操作只有很小的区别。对于任意的 2-3 树，只要对结点进行转换，我们都可以立即派生出一棵对应的二叉查找树。我们将用这种方式表示 2-3 树的二叉查找树称为红黑二叉查找树，简称红黑树。

另一种等价的定义：

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

1. 红链接均为左链接；
2. 没有任何一个结点同时和两条红链接相连；(对应4-结点只是临时结点，不能一直存于2-3树中)
3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。（对应完美平衡的2-3树所有空连接到根的长度相等）

满足这样定义的红黑树和相应的 2-3 树是一一对应的。

无论我们选择用何种方式去定义它们，红黑树都既是二叉查找树， 也是2-3树。因此，如果我们能够在保持一一对应关系的基础上实现2-3树的插入算法，那么我们就能够将二叉查找树中简洁高效的查找方法 和 2-3树中高效的平衡插入算法的优点结合起来。

2.2 颜色表示

为了表示的方便，由于每一个结点都只有一条指向自己的链接（由它的父结点指向它），我们将链接的颜色保存在结点内部一个布尔变量的属性color中。如果指向它的链接为红色，则该属性值为true，黑色则为false。约定空链接为黑色。当说一个结点是红色时，指的是指向它的链接为红色。

2.3 旋转

在对红黑二叉查找树进行的某些操作后，可能会出现红色的右链接或者是两条连续的红链接。出现这些情况后我们必须进行一些操作去修复它。旋转就是红黑二叉查找树修复结构性质的操作，旋转分为左旋转，右旋转。

1. 左旋转：将一条红色的右链接转化为左链接，具体操作过程和操作方法如下左图所示。操作最终将红色链接指向的结点提升为根结点，原来的根结点成为新根结点的左子结点，原来根结点的右链接指向新根结点原来的左子结点；
2. 右旋转：将一条红色的左链接转化为右链接，具体操作与左旋转相反，如下有图所示。

左旋 h 的右链接	左旋 h 的左链接

在插入新的键时我们可以使用旋转操作帮助我们保证 2-3 树和红黑树之间的一一对应关系，因为旋转操作可以保持红黑树的4个重要性质： 有序性，完美平衡性，不存在两条连续的红链接和不存在红色的右链接。在维护红黑树的这些特性时使用的就是左旋转操作，右旋转操作或者是左右旋转操作的组合。再加上一些简单的颜色变换规则就可以很好的实现。

2.4 向底部的2-结点插入新键

在红黑树中插入一个结点与二叉查找树插入的方式是相同的，新键都会在树底部新增一个根结点。为了保证红黑树的性质，**总是使用红链接将新结点和他的父结点相连。**若此时它的父结点是一个2-结点，那么就会出现两种情况。一种是新键小于父结点，这时新结点链接到父结点的红色左链接上成为红色结点。这时刚好可以对应2-3树中的3-结点，不需要变动。如果新键大于父结点，连接在父结点的右链接上，是一个错误的3-结点。这时就需要将这个右红链接左旋转为左红链接修复红黑树。

2.5 向一个3-结点中插入新键

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

1. 新键大于3-结点中的两个键：因此它被连接到 3- 结点的右链接。此时 树是平衡的，根结点为中间大小的键，它有两条红链接分别和较小和较大的结点相连。如果我们将两条链接的颜色都由红变黑，那么我们就得到了一棵由三个结点组成、高为 2 的平衡树。它正好能够对应一棵 2-3 树的4-结点分解为3个2接结点。
2. 新键小于原树中的两个键：它会被连接到最左边的空链接，这样就产生了两条连续的红链接。此时我们只需要将上层的红链接右旋转即可得到第一种情况。
3. 新键介于原树中的两个键之间：这又会产生两条连续的红链接，一条红色左链接接一条红色右链接。此时我们只需要将下层的红链接左旋转即可得到第二种情况。

上述3种情况中第三种情况是最复杂的，我们可以将其转换为第二种情况，第二种情况又可以转换为第一种情况。三种情况的具体转换过程如下图从左到右依次所示。

2.6 颜色变换

如果一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外，我们同时还要将指向它的链接的颜色由黑变红。**这个操作对应了2-3树中非根临时4-结点的分解过程。**这项操作和旋转操作一样是局部变换，不会影响整棵树的黑色平衡性。

2.7 根结点总是黑色

颜色转换会使根结点变为红色。这也可能出现在很大的红黑树中。严格地说，红色的根结点说明根结点是一个 3- 结点的一部分，但实际情况并不是这样。因此我们在每次插入后都会将根结点设为黑色。

2.8 将红链接在树中向上传递

2-3 树中的插入算法需要我们分解 3- 结点，将中间键插入父结点，如此这般直到遇到一个 2-结点或是根结点。我们所考虑过的所有情况都正是为了达成这个目标：每次必要的旋转之后我们都会进行颜色转换，这使得中结点变红。在父结点看来，处理这样一个红色结点的方式和处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上去。具体步骤如下：

1. 如果右子结点是红色的而左子结点是黑色的，进行左旋转；
2. 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转；
3. 如果左右子结点均为红色，进行颜色转换。

三个步骤与下图对应：

2.9 实现

根据上述的描述，一个红黑二叉树的一般实现如下：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

package searching.tree;

public class RedBlackBST {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root; //根结点

    /**
     * 结点静态内部类
     */
    private static class Node {
        private int key;          //结点键
        private String value;     //结点值
        private Node left, right; //指向左右子树的连接
        private int N;            //以该结点为根的子树的结点数
        private boolean color;    //由其父结点指向它的链接的颜色

        Node(int key, String value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
        }
    }

    /**
     * 判断一个结点的颜色是否为红色
     * @param node 结点
     */
    private boolean isRed(Node node) {
        if (node == null) return false;
        return node.color == RED;
    }

    /**
     * 获取当前树的结点数
     */
    public int size() {
        return size(root);
    }
    private int size(Node node){
        if (node == null) return 0;
        else return node.N;
    }

    /**
     * 红色右链接旋转为红色左链接
     * @param oldR 旋转前子树的根节点
     * @return 新子树的根节点
     */
    private Node rotateLeft(Node oldR){
        Node newR = oldR.right;
        oldR.right = newR.left;
        newR.left = oldR;
        newR.color = oldR.color;
        newR.N = oldR.N;
        oldR.color = RED;
        oldR.N = 1 + size(oldR.left) + size(oldR.right);
        return newR;
    }

    /**
     * 红色左链接旋转为红色右链接
     * @param oldR 旋转前子数的根节点
     * @return 新子树的根节点
     */
    private Node rotateRight(Node oldR){
        Node newR = oldR.left;
        oldR.left = newR.right;
        newR.right = oldR;
        newR.color = oldR.color;
        newR.N = oldR.N;
        oldR.color = RED;
        oldR.N = 1 + size(oldR.left) + size(oldR.right);
        return newR;
    }

    /**
     * 颜色转换，子结点变黑，父节点变红
     * @param node 当前结点
     */
    private void flipColors(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }


    /**
     * 根据键值获取节点的值，节点不存在返回NUll
     */
    public String get(int key) {
        Node node = root;
        while (node != null){
            if      (key > node.key) node = node.right;
            else if (key < node.key) node = node.left;
            else return node.value;
        }
        return null;
    }

    /**
     * 查找key，命中更新value，否则新建一个结点
     * @param key 新插入结点的键
     * @param value 新插入结点的值
     */
    public void put(int key, String value){
        root = put(root, key, value);
        root.color = BLACK;
    }
    
    private Node put(Node node, int key, String value){
        //标准插入,和父节点用红链接相连
        if(node == null)
            return new Node(key, value, 1, RED);
        if (key > node.key) node.right = put(node.right, key, value);
        else if (key < node.key) node.left = put(node.left, key, value);
        else node.value = value;
        //调整红黑树
        if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
        if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
        if (isRed(node.left) && isRed(node.right)) flipColors(node);
        node.N = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 中序遍历打印所有节点
     */
    public void inorderPrint(){
        inorderPrint(root);
    }
    
    private void inorderPrint(Node node){
        if (node == null) return;
        inorderPrint(node.left);
        System.out.println(node.key);
        inorderPrint(node.right);
    }

    /**
     * 查看最右侧路径上的节点值
     */
    public void printRight(){
        Node node = root;
        while (node != null){
            System.out.println(node.value);
            node = node.right;
        }
    }
}

除了递归调用后的三条 if语句，红黑树中 put() 的递归实现和二叉查找树中 put()的实现完全相同。它们在查找路径上保证了红黑树和 2-3 树的一一对应关系，使得树的平衡性接近完美。三条if语句分别对应上文红链接向上传递的三种情况。

2.10 性能分析

首先，无论键的插入顺序如何，红黑树都几乎是完美平衡的。这从它和 2-3树的一一对应关系以及 2-3 树的重要性质可以得到。

红黑树的最坏情况是它所对应的 2-3 树中构成最左边的路径结点全部都是 3- 结点而其余均为 2- 结点。最左边的路径长度是只包含 2- 结点的路径长度（～ lgN）的两倍。

和典型的二叉查找树相比，一棵典型的红黑树的平衡性是很好的，在运行中构造的红黑树的路径长度（即查找成本）比初等二叉查找树低 40% 左右。

几种数据结构实现的查找和插入操作效率的对比：

图片资料来自：

1. Algorithms (4th Edition)