从BST到红黑树——易懂版

这篇文章是我自己学习树和红黑树时候的理解，参考了算法第4版，图都是偷的。第1、2节在讲树，第3、4节在给红黑树打基础做铺垫，第5节就是红黑树了。

1 什么是树

长这样的就是树（连通且不含回路的无向图）。它是一种数据结构。

1.1 树的相关术语

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
树叶节点：无子树的节点；
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
树的高度或深度：从根节点到叶子节点的路径的最大值，定义H(null) = -1; H(root) = 0;
森林：由m（m>=0）棵互不相交的树的集合称为森林；

1.2 常见的树

二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一颗二叉树，假设其深度为d(d>=1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
- 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
- 排序二叉树（BST树：Binary Search Tree），也称二叉查找树、二叉搜索树、有序二叉树；
霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

2 父子兄弟树

class TreeNode 
{ 
    Entry entry;
    TreeNode firstChild;
**PtrToNode nextSibling; **
} TreeNode;

应用场景

文件结构
CJSON

3 二叉树

3.1 二叉树的遍历

先序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根

“序”可理解为相对为“根”的顺序
层序遍历：一层层来

3.1.1 先/中/后序遍历

先序遍历结果：A B D E G I C F H J

中序遍历结果：D B E I G A C H J F

后序遍历结果：D I G E B J H F C A

代码：

public void pre_order (BinaryTreeNode root) {
    if (root == null) return;
    
    print(root.value); //打印当前值
    pre_order(root.left); //打印左子树
    pre_order(root.right); //打印左子树
}

3.1.2 层序遍历

利用队列实现：

先将根节点入队，开始循环：如果队列里有元素，则执行出队（打印）操作，并将该出队元素的左子节点和右子节点（如果有）入队，当队列为空，遍历结束。

3.1.3 根据遍历结果构造树

给出一棵二叉树的先序（或后序）遍历结果，以及中序遍历结果，构造树。先序+中序遍历与后序+中序遍历构造树原理几乎一致，该算法的关键是中序遍历。下以后序+中序遍历为例。

显然，后序遍历的最后一个元素即为整棵树的根节点，即后序遍历数组的最后一个值就是根，根据此元素在中序遍历数组中的位置，可以把中序遍历数组划分为左子树的中序遍历子数组和右子树的中序遍历子数组。左子树的中序遍历数组的n个数对应后序遍历数组的前n个数，右子树的中序遍历数组的m个数对应后序遍历数组的第n+1~第n+m个数。那么后序遍历数组的第n个数即为左子树的根节点，第n+m个数即为右子树的根节点，递归构造即可。

例子：

中序遍历结果：D B E I G A C H J F

后序遍历结果：D I G E B J H F C A

3.2 二叉树的表示

3.2.1 链式表示

自定义类TreeNode，属性一般来说有该节点的值和指向下一个节点的链接

3.2.2 数组表示

若根节点从index为1开始，那么第i个节点的左子节点编号为2i，右子节点编号为2i+1，父节点为i/2（思考为什么？）

3.3 二叉树的高度

一棵二叉树的高度定义为该树根节点到所有叶子节点的路径中的最大值

定理：一棵二叉树的节点个数不超过 $n(T)\leq2^{h(T)+1}-1$ （其中n(T)为树T的节点个数，h为树高度）

证明：数学归纳法证明：树高为0和1时，显然成立。假设该定理对所有h≤H的树成立，当h=H+1时，

$n(T)=1+n(T1)+n(T2)$

$\leq1+2^{h(T1)+1}-1+2^{h(T2)+1}-1$

$\leq2*max(2^{h(T1)+1},2^{h(T2)+1})-1$

$=2*2^{max(h(T1)+1,h(T2)+1)}-1$

$=2*2^{h(T)-1}-1$

$=2^{h(T)+1}-1$

4 树与查找

4.1 符号表

4.1.1 什么是符号表

可以理解为一张抽象的表格，我们将信息（值）被存放在其中并通过索引（键）来访问，符号表最主要的目的就是将一个键和一个值联系起来，使用者能够将一个键值对插入符号表并希望之后能够从符号表的所有键值对中按照键直接找到对应的值。例如一个数组，其中元素的下标就是键，元素就是值，我们可以直接通过索引访问数组元素。

符号表的增删改查操作，实际上都是基于查找来实现的，插入操作要先查找到该插入的位置才能插入，删除要先找到要删除的键才能删除，所以要实现一张符号表，实现查找算法是基础。

如果就用数组这种数据结构来存放键值对，其效率不尽如人意，例如假如要找的值是最后一个，必须先遍历整个数组。由此可见，想要高效的实现查找算法，首先必须得定义良好的数据结构。

4.1.2 符号表常用的API

4.2 二叉查找树

定义：一棵二叉查找树(BST, Binary Search Tree)是一棵二叉树，其中每个节点都含有一个Comparable的键(以及与其相关联的值)，且每个节点的左子树的所有键都比它大，右子树的所有键都比它小。

4.2.1 基于二叉查找树的符号表

public class BST<Key extends Comparable<Key>, Value>{
    private Node root;
    
    private class Node{
        private Key key;//键
        private Value val;//值
        private Node left, right;//指向子树的链接
        private int N;//以该节点为根节点的树中的节点总数
        
        public Node(Key key, Value val, int N){
            this.key = key; this.val = val; this.N = N;
        }
    }
    
    public int size(){
        return size(root);
    }
    
    private int size(Node x){
        if(x == null) return 0;
        return x.N;
    }
}

4.2.2 构造

构造一棵BST的过程就是不断插入节点的过程

4.2.3 查找和插入

在二叉查找树中查找的递归算法：

（1）如果树是空树，则查找未命中

（2）如果被查找的键和某结点的键相等，则查找命中，否则递归的在子树中查找

（3）被查找的键比当前根节点更小就选择左子树，否则选择右子树

从根节点开始，在每个节点中查找的过程都会递归地在它的一个子节点上展开，因此一次查找也就定义了树的一条路径。对于命中的查找，路径在含有被查找的键的节点处结束，对于未命中的查找，路径终点是一个空链接

BST一个重要的特性是对于插入操作，其实现难度和查找差不多：

（1）若待插入的节点不存在于树中，那么查找会结束于一条空链接，这时将该空链接指向待插入的节点即可

（2）若待插入的节点已存在，查找命中，则更新其值

public Value get(Key key){
    return get(root, key);
}

private Value get(Node x, Key key){
    if (x == null) return null;
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) return get(x.left, key);
    else if (cmp > 0) return get(x.right, key);
    else return x.val;
}

public void put(Key key, Value val){
    root = put(root, key, val);//直接更新整棵树
}

private Node put(Node x, Key key, Value val){
    //如果key存在于以x为根节点的子树中则更新其值，否则把以key和val为键值对的新节点插入到该子树中
    if(x == null) return new Node(key, val, 1);
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else x.val = val;
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

4.2.4 查找的性能分析

二叉查找树的查找算法运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。

最好情况：一棵含有N个节点的树是完全平衡的，每条空链接和根节点的距离都为~lgN
最坏情况：搜索路径上有N个节点，树是“一边倒”的
一般情况：与最好情况更接近

4.2.5 有序性相关的方法与删除操作

4.2.5.1 最大键和最小键

如果根节点的左链接为空，则一棵二叉查找树中最小的键就是根节点
如果根节点的左链接非空，则树中的最小键就是左子树的最小键

最大键的查找就是将左子树改为右子树即可

public Key min() {
    return min(root).key;
}

private Node min(Node x) {
    if (x.left == null) return x;
    return min(x.left);
}

4.2.5.2 向上取整和向下取整

按照符号表API，floor(key)表示小于等于key的最大键，即向下取整

如果给定的key小于二叉查找树根节点的键，那么小于等于key的最大键一定在根节点的左子树中
如果给定的key大于二叉查找树的根节点
- 当根节点右子树中存在小于等于key的键时，小于等于key的最大键才会出现在右子树中
- 否则根节点就是小于等于key的最大键

向上取整则反过来即可

    public Key floor(Key key) {
        Node x = floor(root, key);
        if (x == null) return null;
        return x.key;
    }

    private Node floor(Node x, Key key) {
        if (x == null) return null;
        
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp < 0) return floor(x.left, key);
        Node t = floor(x.right, key);
        if (t != null) return t;
        else return x;
    }

4.2.5.3 选择第k大的键

找到排名为k的键(即树中正好有k个小于它的键)

如果左子树中的节点数t大于k，则递归地在左子树中寻找排名为k的键
如果t=k，则返回该根节点的键
如果t<k，则递归地在右子树中寻找排名为k的键

    public Key select(int k) {
        return select(root, k).key;
    }

    private Node select(Node x, int k) {
        if (x == null) return null;

        int t = size(x.left);
        if (t > k) return select(x.left, k);
        else if (t < k) return select(x.right, k - t - 1);
        else return x;
    }

4.2.5.4 排名

排名是选择第k大的键的逆方法，给定一个键，返回比其小的键的数目，即给定键的排名。

如果给定键和根节点键相等，则返回左子树中的结点总数t
如果给定键小于根节点键，则返回该键在左子树中的排名（递归计算）
如果给定键大于根节点键，则返回t+1+(该键在右子树的排名(递归计算))

public int rank(Key key) {
        return rank(key, root);
    }

    private int rank(Key key, Node x) {
        if (x == null) return 0;
        
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return rank(key, x.left);
        else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
        else return size(x.left);
    }

4.2.5.5 删除最大键和删除最小键

删除操作往往是最难实现的，作为热身，先考虑删除最小值和删除最大值操作，作为删除操作基础。

删除最小值：不断深入根节点的左子树直至遇见一个空链接，然后将指向该节点的链接指向该节点的右子树( 如何实现？)，此时已经没有任何链接指向要被删除的节点，因此它会被GC清理掉。
删除最大值：与删除最小值类似

    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

4.2.5.6 删除

要想删除某个节点后仍然维持二叉查找树的特性，首先得确定删除操作的规则：

若要删除的节点没有子节点或只有一个子节点，则直接删除即可
若要删除的节点有两个子节点，那么用该节点的后继节点，即用右子树中的最小节点将其替换即可

用四个简单的步骤就可以完成将待删除节点：

将被删除的节点x保存为t
把x变成它的后继节点min(t.right)
将x的右链接指向deleteMin(t.right)
将x的左链接（本为空）设为t.left

这几步操作其实也很好理解，要删掉节点x，也就是要把x从树中移除，那肯定就要找一个节点替代x的位置，这个替代x位置的节点就是x的右子树中的最小节点。为什么呢？因为x的左子树的所有节点都比x小，x的右子树的所有节点都比x大，而你会发现，x的右子树的最小节点min(t.right)也满足这个条件！x左子树的所有节点都比它小，x右子树的所有其它节点都比它大，拿走x以后，它是不是替代x的最佳人选？这样保证了树的有序性。

实现起来的话，先将x保存为t，然后将x设为min(t.right)。deleteMin(t.right)会返回删掉t右子树的最小节点之后的树的根节点，那么将x的右链接指向deleteMin(t.right)，x的左链接指向t.left，就实现了上面的想法。

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

4.2.6 性能分析

命题：在一棵二叉查找树中，所有操作在最坏情况下所需时间均和树高度成正比

证明：树的所有操作都沿着树的一条或两条路径行进，路径的长度不可能大于树的高度

二叉查找树的基本实现的良好性能依赖于其中的键的分布足够随机以消除长路径，但在最坏情况下，其恶劣的性能仍然是不能被接受的，接下来将会介绍一种改进的数据结构——平衡查找树。

4.3 平衡查找树

由于二叉查找树的相关操作最坏情况下仍可能为线性级别，下面将介绍一种二叉查找树——平衡查找树，它将保证无论如何构造它，运行时间都是对数级别的。

在一棵含有N个节点的树中，我们希望树高为~lgN，这样就能保证所有查找都能在~lgN次比较内结束，不幸的是，在动态插入中保证树的完美平衡的代价实在太高了，所以，我们先稍稍放松完美平衡的要求，介绍一种保证符号表的所有操作（范围查找除外）都能在对数时间内完成的数据结构。

4.3.1 2-3 查找树

为保证查找的平衡性，我们需要一些灵活性，因此在这里我们允许树的一个节点保存多个值（多路查找树）

把一棵标准的二叉查找树中的节点称为2-节点，它含有一个键和一条链接
- 左链接指向的子树的所有节点都小于该节点
- 右链接指向的子树的所有节点都大于该节点
引入3-节点，它含有两个键和三条链接
- 左链接指向的子树的所有节点都小于该两个节点
- 中链接指向的子树的所有节点都位于该两个节点之间
- 右链接指向的子树的所有节点都大于该两个节点

4.3.1.1 查找

先将待查找的键和根节点的键比较，如果（和其中任意一个）相等，则查找命中
否则根据比较结果找到相应区间，递归地在其相应区间的子树中继续查找
直到找到空链接，则查找未命中

4.3.1.2 向2-节点中插入新键

和二叉查找树一样，插入操作我们可以先进性一次未命中查找，然后将待插入的新键直接挂在树的底部，但这样就破坏了完美平衡性。利用好2-3树，我们就可以在插入后继续保持完美平衡。如果未命中查找结束于2-节点，只需将该2-节点变为3-节点即可。

4.3.1.3 向3-节点中插入新键第一轮热身：向一棵只含有一个3-节点的树中插入新键

讨论一般情况之前，先来看比较简单的，向一棵只含有一个3-节点的树中插入新键。这个节点已经有两个键，已经没有可插入的地方，那么为了将新键插入，我们临时地把这个节点变成一个4-节点，然后再将4-节点分解为新的2-3树。这个例子虽然很简单，但却告诉了我们2-3树是如何生长的。插入前树高为0，插入后树高为1

4.3.1.4 向3-节点中插入新键第二轮热身：向一个父节点为2-节点的3-节点中插入新键

第二轮热身，假设未命中查找结束于一个3-节点，而其父节点是一个2-节点，我们的目的是在维持树的完美平衡下为新键腾出空间。思路是先像刚才一样构造一个4-节点，再将4-节点分解为一个根节点和两个子节点，然后再将分解出来的那个根节点挤到上面的父节点中，借助图很好理解。

这次转换并不影响完美平衡的2-3树的主要性质：

树仍然是有序的，因为中键被移到父节点中去了
树仍然是完美平衡的，插入后所有空链接到根节点距离仍相同

这次转换是2-3树动态变化的核心

4.3.1.5 向3-节点中插入新键第三轮热身：向一个父节点为3-节点的3-节点中插入新键

第三轮热身，假设未命中查找结束于一个3-节点，而其父节点也是一个3-节点。我们将重复执行4.3.1.4中的操作，将所有构造的临时的4-节点不断分解，并将中键插入更高层的父节点，直至遇到一个2-节点或者到达3-节点的根

4.3.1.6 向3-节点中插入新键第四轮热身：分解根节点

如果从插入节点到根节点的路径上全部是3-节点，根节点将最终变为一个4-节点，那么就需要分解根节点，将临时的4-根节点分解为三个2-节点，树高加1，这次变换仍然保证了树的完美平衡性，因为其变换的是根节点

4.3.1.7 向3-节点中插入新键第五轮热身：分解临时的4-节点的所有情况（局部变换）

2-3树的插入算法的根本在于这些变换是局部的。除了相关的节点和链接之外不必修改或者检查树的其他部分，每次变换中，变更的链接数量不会超过一个很小的常数。

至此，2-3树的向3-节点中插入新键的所有情况已经介绍完毕，需要特别指出的是，这些变换是局部的，不会影响全局的有序性和平衡性：

任意空链接到根节点的路径长始终都是相等的
如果不是根节点分解，那么变换之前根节点到所有空链接路径长为h，变换后该长度仍然为h，只有当根节点分解，树高才加1

4.3.1.8 2-3树小结

和标准的二叉查找树由上而下的生长方式不同，2-3树是从下往上生长的，再来看一组示例来理解2-3树。

从上面的示例可以看出，如果是二叉查找树的最坏情况，即按升序插入会得到一棵高度为9的树，但是如果是在2-3树面前，树的高度仅为2。我们可以确定2-3树在最坏情况下仍有较好的性能，任何查找或者插入的成本都不会超过对数级别。一棵含有10亿个节点的2-3树高度可以仅在19~30之间，最多访问30个节点就可以在10亿个键中进行任意查找和插入，这是相当惊人的！

但是，2-3树由于其节点的复杂性，我们需要维护两种不同的节点，在代码实现上会遇到困难，还可能产生额外的开销，因此，我们需要稍微做一点点改进

4.3.2 红黑树

上述2-3树的算法思路并不难理解，但是实现较为困难，因此引入红黑树来实现它。

4.3.2.1 红黑树与2-3树

红黑树用给普通二叉查找树的节点标上红黑两种颜色的方式来替换2-3树中的2-节点和3-节点：

红链接将两个2-节点连接起来构成一个3-节点
黑链接则是2-3树中的普通链接

这种表示法的优点之一是，我们无需修改就可以直接使用之前二叉查找树的get()方法

注：有些资料中的红黑树是红节点和黑节点，这与红链接和黑链接并不冲突，指向该节点的链接是红色则为红节点，指向该节点的链接是黑色则为黑节点。

红黑树的定义：

含有红黑链接并满足以下条件（思考为什么？）的二叉查找树：

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

红黑树与2-3树一一对应：

如果将一棵红黑树的节点画平，那么所有的空链接到根节点的距离都是相同的。如果将红链接合并，那得到的就是一棵2-3树。无论怎么描述，红黑树都既是二叉查找树，又是2-3树，因此，我们就可以将二者优点结合起来，即二叉查找树中高效的查找方法以及2-3树中高效的平衡插入算法

颜色表示：

前已说明，一个节点是红节点当且仅当指向它的链接是红链接，一个节点是黑节点当且仅当指向它的链接是黑链接。为了编程的方便，我们将链接的颜色保存在节点Node的属性color中，color定义为boolean类型：

true为红色
false为黑色（空链接也为黑色）

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;

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

    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;
        private boolean color;

        public Node(Key key, Value val, int N, boolean color) {
            this.key = key;
            this.val = val;
            this.N = N;
            this.color = color;
        }
    }

    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == RED;
    }
}

红黑树相关操作的核心：先操作，后调整（后面会逐渐理解这句话）

4.3.2.2 旋转

在我们进行某些操作的时候可能会出现红色右链接或者两条连续的红链接，我们需要对上述情况进行修复，修复的方法就是旋转。旋转操作可以改变红链接的指向。

左旋转：将红色右链接变为红色左链接

    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

右旋转：将红色左链接变为红色右链接

    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

旋转操作仍然可以保证2-3树与红黑树之间的一一对应关系以及有序性和完美平衡性，因此它是我们想要的操作。下面来看看如何使用旋转操作保持红黑树的两个重要性质：不存在连续两条红链接、不存在红色右链接

4.3.2.3 热身一：向单个2-节点插入新键

如果新键小于老键，只需新增一条向左的红链接以及一个节点即可
如果新键大于老键，则插入会产生一条红色右链接，那么我们使用左旋来将其修正为红色左链接

左旋操作使用 root = rotateLeft(root) 即可

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

4.3.2.4 热身二：向一个3-节点中插入新键

有三种情况：

新键小于两个键
新键介于两键之间
新键大于两键

我们可以分别使用0次，1次，2次旋转来保证插入的正确性

4.3.2.4 热身三：颜色转换

从上面看到，如果一个2-节点的两条红链接都是红色，我们就将那两个链接都变为黑色，并将该2-节点变为红色。这项操作也是一个局部变换，不会影响整棵树的黑色平衡性

    private void flipColors(Node h) {
        //1个4-节点和2个2-子节点的互换
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }

4.3.2.5 热身四：根节点总是黑色

颜色转换可能使根节点变为红色，红色的根节点说明根节点是一个3-节点的一部分，但实际情况并不是这样，因此每次插入后都会将根节点设置为黑色

4.3.2.6 热身五：向树底部的3-节点插入一个新键

4.3.2.7 热身六：向上传递

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

只要使用好左旋转、右旋转以及颜色转换这三种简单的操作，我们就可以保证插入后红黑树和2-3树的一一对应关系。在沿着插入点到根节点的路径向上移动时在所经过的每个节点顺序完成以下操作，我们就能完成红黑树的插入操作：

如果右子节点是红色的而左子节点是黑色的，进行左旋转
如果左子节点是红色的且它的左子节点也是红色的，进行右旋转
如果左子节点和右子节点均为红色，进行颜色转换

4.3.2.8 红黑树插入操作的完整实现

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;

    private class Node 

    private boolean isRed(Node x) 
    private Node rotateLeft(Node h) 
    private Node rotateRight(Node h)
    private void flipColors(Node h)
    private int size(Node x) 

    public void put(Key key, Value val) {
        root = put(root, key, val);
        root.color = BLACK;//修正根节点为黑色
    }

    private Node put(Node h, Key key, Value val) {
        if (h == null) {
            return new Node(key, val, 1, RED);
        }

        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, val);
        } else if (cmp > 0) {
            h.right = put(h.right, key, val);
        } else {
            h.val = val;
        }

        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
}

4.3.3 红黑树的删除操作

4.3.3.1 删除最小键

从树底部删除最小键，如果该节点是个3-节点，直接删除即可，但如果是2-节点，则直接删除后会导致红黑树的黑高不等，平衡性被破坏，所以，为了保证删除的不会是2-节点，我们沿着左链接向下变换，确保当前节点不会是2-节点（可能是3-节点，也可能是临时的4-节点）。

根节点的情况：
- 如果根节点是2-节点，左右子节点都是2-节点，那么直接将这三个2-节点变为一个4-节点即可
- 否则为了保证根节点的左子节点不是一个2-节点，我们需要从右边“借”一个键来

沿着左链接向下变换的过程中：
- 如果当前节点的左子节点不是2-节点，完成
- 如果当前节点的左子节点是2-节点而它的亲兄弟节点不是2-节点，则将兄弟节点的一个键移到左子节点中
- 如果当前节点的左子节点和它的兄弟节点都是2-节点，则将左子节点、父节点中的最小键（父节点已经不是2-节点）和左子节点最近的兄弟节点合并为一个4-节点，这使父节点由一个4-节点变为一个3-节点或者由一个3-节点变为一个2-节点

遍历到最后，我们能够得到一个含有最小键的3-节点或者4-节点，然后我们就可以直接将最小键从其中删除。注意：完成删除最小键操作后，要向上分解所有临时的4-节点。

理解代码的注意事项：

注意"! isRed"是指2-节点
注意区别红黑树的节点和2-3树的节点（用2-3树的思想，看BST的代码）
注意区别红黑树的根节点和2-3树的根节点
注意红黑树的性质

    public void deleteMin() {
        //入口函数，如果根节点的左右子节点都是2-节点，将根节点变红
        //该操作保证了从入口函数进入递归函数的root一定是3-节点或者4-节点的一部分，因为根据我们的分析，从根节点开始就要保证当前节点不为2-节点
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        //删掉最小值，返回新树
        root = deleteMin(root);
        //将红黑树的根节点重新变回黑色，即2-节点，因为红黑树的根节点总为黑色
        if (root != null) {
            root.color = BLACK;
        }
    }

    //isRed(x.left)&&!isRed(x)表示x为3-节点的一部分
    //isRed(x.left)&&isRed(x)表示x为4-节点的一部分
    //!isRed(x.left)&&!isRed(x)表示x为2-节点
    //!isRed(x.left)&&isRed(x)表示x不为2-节点且x左子节点为2-节点
    private Node deleteMin(Node h) {
        if (h.left == null) return null;
        
        //如果当前节点（2-3树）的左节点是2-节点，那么进行变换
        if (!isRed(h.left) && !isRed(h.left.left)) {
            h = moveRedLeft(h);
        }
        h.left = deleteMin(h.left);
        return balance(h);
    }

    private Node moveRedLeft(Node h) {
        flipColors(h);
        if (isRed(h.right.left)) {
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
        }
        return h;
    }

    private Node balance(Node h) {
        if (isRed(h.right)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

4.3.3.2 删除

    private Node moveRedRight(Node h) {
        flipColors(h);
        if (isRed(h.left.left)) {
            h = rotateRight(h);
        }
        return h;
    }

    public void deleteMax() {
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = deleteMax(root);
        if (root != null) {
            root.color = BLACK;
        }
    }

    private Node deleteMax(Node h) {
        if (isRed(h.left)) {
            h = rotateRight(h);
        }
        if (h.right == null) {
            return null;
        }
        if (!isRed(h.right) && !isRed(h.right.left)) {
            h = moveRedRight(h);
        }
        h.right = deleteMax(h.right);
        return balance(h);
    }

    public void delete(Key key) {
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = delete(root, key);
        if (root != null) {
            root.color = BLACK;
        }
    }

    private Node delete(Node h, Key key) {
        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left)) {
                h = moveRedLeft(h);
            }
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left)) {
                h = rotateRight(h);
            }
            if (key.compareTo(h.key) == 0 && h.right == null) {
                return null;
            }
            if (!isRed(h.right) && !isRed(h.right.left)) {
                h = moveRedRight(h);
            }
            if (key.compareTo(h.key) == 0) {
                h.val = get(h.right, min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else {
                h.right = delete(h.right, key);
            }
        }
        return balance(h);
    }
}