1. 二叉查找树

概述

我们来思考这么一个问题，如何在n 个动态的整数中搜索某个整数？（查看其是否存在）
看着还是很简单的，以动态数组存放元素，从第0个位置开始遍历搜索，运气好的话，第一个就找到了，运气差的话，可能找到最后都找不到，算一下的话平均时间复杂度是 O(n)，数据规模大的话，是比较慢的
再好一点的话，上一篇 二分查找及其变种算法 说到了，使用二分查找的话，效率是很高的，最坏时间复杂度：O(logn)，不怕你数据规模大，但是我们要注意一点，这是一个动态的序列，而前面也说到了二分查找针对的是有序集合，那么维护这样的一个有序的集合，每次修改数据，都需要重新排序，添加、删除的平均时间复杂度是O(n)，对于这种动态的数据集合，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。
那么针对这个需求，有没有更好的方案？能将添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)，主角登场，二叉搜索树可以办到。

二叉查找树 - Binary Search Tree: 也称二叉搜索树、有序二叉树, 二叉排序树。对于根树和所有子树都满足，每个节点都大于左子树元素，而小于右子树元素，且没有键值相等的结点
搜索、插入、删除的复杂度等于树高，期望 ，最坏 O(n)（数列有序，树退化成线性表）

二叉查找树动态展示: visualgo.net/zh/bst

图解：

性质：

• 任意一个节点的值都大于其左子树所有节点的值
• 任意一个节点的值都小于其右子树所有节点的值
• 它的左右子树也是一棵二叉搜索树

使用二叉搜索树可以大大提高搜索数据的效率，同时也需要注意一点，二叉搜索树存储的元素必须具备可比较性，同时不能为null， 比如int、double等，如果是自定义类型，需要指定比较方式，这一点在后面会仔细讲到

设计

属性与方法

属性：

//接收用户自定义比较器
private Comparator<E> comparator;

公开方法：

• void add(Eelement) —— 添加元素
• void remove(Eelement) —— 删除元素
• boolean contains(Eelement)—— 是否包含某元素

在基于二叉树的基础上，只需要增加上面这3个接口方法，看完这些方法设计，与之前编写的动态数组，链表是不是有一些区别，没错，少了index，对于我们现在使用的二叉树来说，它的元素没有索引的概念，为什么？我们不是可以按照从上到下，从左到右，进行编号吗？例如下图：

但是这样不对，没有意义，比如，我们再一个添加，11,15的元素进来，按照二叉排序树，11 > 8 —> 往右子树走，11 > 10 —> 在往右走，11 < 14 —> 往左走，11 < 13 —>往左走，发现没有元素，插入该位置，15也是一样，那么得出来的结果应该是：

这样的编号索引与我们之前数组与链表的先入先编号是不一样，所以在二叉搜索树中没有索引的概念

Add方法

方法步骤：
1、找到父节点parent
2、创建新节点node
3、parent.left = node或者parent.right=node
注意点：如果要插入的值相等的元素该如何处理？

• 直接return，不作处理
• 覆盖原有节点 （建议）

我们一步一步来，首先，我们前面说到，添加的元素必须具备可比较性，所以不能为null，这样我们需要一个元素非空检查的方法

/**
 * 新节点元素非空检查
 * @param element
 * @return
 */
private void elementNotNullCheck(E element){
    if (element == null){
        throw new IllegalArgumentException("element must not be null");
    }
}
复制代码

接下来我们开始找父节点parent，这里要注意的是，遍历查找父节点时，我们是从根节点root开始，如果当前是空树，那么不用找，直接新节点就是根节点，如果树不为空，那么我们就要从根节点开始找父节点，这是我们重点分析的地方
前面说到了，二叉搜索树存储的元素必须具备可比较性，在这里就体现了，找寻父节点的过程就是我们不断比较的过程，所以我们还需要一个比较方法，用于比较两个元素的大小

/**
 * 比较函数，返回0，e1==e2;返回值大于0，e1>e2;返回小于0，e1<e2
 * @param e1
 * @param e2
 * @return
 */
private int compare(E e1,E e2){
    return 0;
}
复制代码

方法的逻辑我们先不写，这是因为我们的二叉树在设计上是泛型类，是支持存储任意类型的。对于Java官方提供的int、double这种基本的数值类型，或者是Integer、Double、String这些实现了比较接口的Comparable来说，比较逻辑是很好写的，但是对于我们自定义的类，比如Person来说，这是不行的，因为不具备可比较性，同时我们也不知道比较规则

public class BinarySearchTree<E> {
    //...
}
复制代码

public class Person {
    /**
     * 年龄
     */
    private int age;
    public Person(int age) {
        this.age = age;
    }
}
复制代码

针对上面说到缺点，我们可以通过以下方法解决：
1、强制要求实现java.lang.Comparable接口，重写public int compareTo(T o);方法，自定义比较规则

public class BinarySearchTree<E extends Comparable<E>>{
    //....
}
复制代码

例如：Person 类

public class Person implements Comparable<Person> {
    private int age;
    public Person(int age) {
        this.age = age;
    }
    /**
     * 自定义比较规则
     * @param p
     * @return
     */
    @Override
    public int compareTo(Person p) {
        return Integer.compare(age, p.age);
    }
}
复制代码

这样子就可以在BinarySearchTree二叉搜索树中的compare方法中调用重写的compareTo方法，实现比较逻辑，但是这样写有一些不好的地方，比如说，对于传入的类型进行了强制要求，同时，由于比较规则是编写在Person类中的，对于一个类来说只能自定一种比较规则，很不方便。
2、编写实现java.util.Comparator接口的匿名内部类，重写int compare(T o1, T o2);方法
同时在BinarySearchTree类中，添加接收用户自定义比较器的属性，这样做能可以实现按照自定义规则，编写不同的比较器

//接收用户自定义比较器
private Comparator<E> comparator;
/**
 * 构造函数
 * @param comparator
 */
public BinarySearchTree2(Comparator comparator) {
    this.comparator = comparator;
}
复制代码

这时候，只需要在实例化二叉搜索树时，传入比较器就行，例如;

BinarySearchTree<Person> bSTree = new BinarySearchTree<>(new Comparator<Person>() {
    //自定义比较规则
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge() - o2.getAge();
    }
});
复制代码

但是，这样子还是不好，因为在实例化时，如果没有传入比较器，编译器检测就会报错，那么就有了第3种方法
3、保留Comparable和Comparator接口，同时提供无参构造，与带参构造

/**
 * 无参构造
 */
public BST() {
    this(null);
}
/**
 * 构造函数
 * @param comparator
 */
public BST(Comparator<E> comparator) {
    this.comparator = comparator;
}
复制代码

这样的话，如果用户有传入比较器的话，就用比较器，没有的话默认用户实现了Comparable接口，对传入的类强转为Comparable，如果都没有，自然会编译错误，抛出异常。这样BinarySearchTree中的compare应该这么写:

/**
 * 比较函数，返回0，e1==e2;返回值大于0，e1>e2;返回小于0，e1<e2
 * @param e1
 * @param e2
 * @return
 */
private int compare(E e1,E e2){
    if (comparator != null){
        return comparator.compare(e1,e2);
    }
    return ((Comparable)e1).compareTo(e2);
}
复制代码

完成了这些就是添加节点方法了，实现了上面的函数后，其实就很好写了，无非就是小的往左，大的往右，等于的的覆盖
add方法

/**
 * 向二叉树添加节点
 * @param element
 */
public void add(E element){
    elementNotNullCheck(element);
    //空树，添加第一个节点
    if (root == null){
        root = new Node<>(element,null);
        size++;
        return;
    }
    //非空树情况,找到其父节点
    Node<E> node = root;
    //记住找到的父节点，默认根结点
    Node<E> parent = root;
    //记住最后一次的比较情况
    int cmp = 0;
     while (node != null){
        cmp = compare(element,node.element);
        if (cmp > 0){
            parent = node;
            //大于父节点值，取右子节点比较
            node = node.right;
        }else if (cmp < 0){
            parent = node;
            //小于父节点值，取左子节点比较
            node = node.left;
        }else {
            //相等，第1种处理方法，不处理
            //return;
            //相等，第2种处理方法，覆盖原有节点
            node.element = element;
        }
     }
     //插入新节点
     Node<E> newNode = new Node<>(element,parent);
     if (cmp > 0){
        parent.right = newNode;
     }else {
         parent.left = newNode;
     }
     size++;
}

Remove方法

方法步骤：
1、根据传入的元素查找节点
2、将找到的节点删除
大体上是这两个步骤，先分析一下第一个步骤，实际上就是我们前面思考题中说到的查找算法嘛，实现起来也比较简单，因为我们的二叉搜索树都是排序好的，上代码：

/**
 * 查找元素为element的节点
 * @param element
 * @return
 */
private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        int cmp = compare(element, node.element);
        if (cmp == 0) return node;
        if (cmp > 0) {
            node = node.right;
        } else {
            // cmp < 0
            node = node.left;
        }
    }
    return null;
}

有了node方法,我们的contains方法也很好写了，直接调用就可以了

/**
 * 判断树是否包含值为element的节点
 * @param element
 * @return
 */
public boolean contains(E element) {
    return node(element) != null;
}

删除找到的节点，这里比较复杂了，根据节点的度，有以下三种情况：
1、叶子节点

2、度为 1 的节点：

2、度为 2 的节点：

删除节点度为2的节点，做法是找到它的前驱节点，或者后继节点，例如上图，要删除的节点是5，按照二叉搜索树的规则，要找到一个节点代替5的位置，使其程成为一个新的二叉搜索树，那么这个节点就是要删除的节点的左子树节点的最大值，或者右子树的最小值，也就是器前驱节点，或者后继节点，这里如果不熟悉的回去上一篇深入理解二叉树 翻一翻相关概念
上代码咧：

/**
 * 删除元素为element的节点
 * @param element
 */
public void remove(E element) {
    remove(node(element));
}
/**
 * 删除传入的节点
 * @param node
 */
private void remove(Node<E> node) {
    if (node == null) return;
    size--;
    // 删除度为2的节点，实际上是转化为删除度俄日1或者0node节点
    if (node.hasTwoChildren()) {
        // 找到后继节点
        Node<E> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.element = s.element;
        // 删除后继节点
        node = s;
    }
    // 删除node节点（node的度必然是1或者0）
    Node<E> replacement = node.left != null ? node.left : node.right;
    // node是度为1的节点
    if (replacement != null) {
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度为1的节点并且是根节点
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
    } else if (node.parent == null) { // node是叶子节点并且是根节点
        root = null;
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
    }
}

小结

二叉搜索树能将添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)，由于二叉搜索树的排序性质，无论是添加、删除、查找，从根节点开始，根据小向左，大向右的情况，每向下一层，都会淘汰掉令一半的子树，这是不是跟二分搜索特别的像，再差就是查找到树的最底层，所以说添加、删除、搜索的时间复杂度都可优化到O(logn)

2. 平衡二叉查找树

为什么需要平衡二叉查找树？二叉查找树在理想情况下，插入、删除、查找操作的时间复杂度都是O(logn)，但是二叉查找树在频繁的动态跟新过程中，会出现退化情况，最差情况时，退化为链表。为了解决这个复杂度退化问题，所以需要平衡二叉查找树。
平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1，完全二叉树、满二叉树都是平衡二叉树。
平衡二叉查找树：满足平衡二叉树的二叉查找树。AVL 树、Treap（树堆）、Splay Tree（伸展树） 是严格的平衡二叉查找树。红黑树是不严格的。

3. 红黑树

性质

红黑树 - Red–black tree 是一种自平衡二叉查找树，除了符合二叉查找树的性质外，它还满足以下五条性质:

1. 每个结点要么是红的，要么是黑的
2. 根结点是黑的
3. 每个叶子结点是黑的（叶子结点指树尾端 NIL 指针或 NULL 结点，不包含数据，只充当树在此结束的指示）
4. 如果一个结点是红的，那么它的两个子节点都是黑的 (从根到每个叶子的所有路径上不能有两个连续的红色节点)
5. 对于任一结点而言，其到叶结点树尾端 NIL 指针的每一条路径都包含相同数目的黑结点

平衡优势

上述约束确保了红黑树的关键特性: 从根到叶子的最长路径不会超过最短路径的两倍
证明: 主要看性质 4 和 性质 5，假设从根到叶子的最短路径 a 上有黑色节点 n 个，最长路径 b 肯定是交替的红色和黑色节点，而根据性质 5 可知从根到叶子的所有路径都有相同数目的黑色节点， 这就表明 b 的黑色节点也为 n 个，但 b 出现的红色节点不可能超过黑色节点个数，否则会破坏性质 4 (抽屉原理)，所以从根到叶子的最长路径不会超过最短路径的两倍

调整

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。 恢复红黑树的性质需要少量 的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为 次。
红黑树发生变更时需要 [变色] 和 [旋转] 来调整，其中旋转又分 [左旋] 和 [右旋]。

• 变色就是更改颜色
• 左旋: 以 X 为支点逆时针旋转红黑树的两个节点 X-Y，使得父节点被自己的右孩子取代，而自己下降为左孩子

• 右旋: 以 X 为支点顺时针旋转红黑树的两个节点 X-Y，使得父节点被自己的左孩子取代，而自己下降为右孩子

旋转过程中只需要做三次指针变更就行

插入和删除

插入节点

插入节点的位置跟二叉查找树的寻找方法基本一致，如果插入结点 z 小于当前遍历到的结点，则到当前结点的左子树中继续查找，如果 z 大于当前结点，则到当前结点的右子树中继续查找， 如果 z 依然比此刻遍历到的新的当前结点小，则 z 作为当前结点的左孩子，否则作为当前结点的右孩子。而红黑树插入节点后，为了保持约束还需要进行调整修复(变色加旋转)。
所以插入步骤如下: 红黑树按二叉查找树的规则找到位置后插入新节点 z，z 的左孩子、右孩子都是叶子结点 nil， z 结点初始都为红色，再根据下述情形进行变色旋转等操作，最后达到平衡。

• 情形 1: 如果当前节点是根结点，为满足性质 2，所以直接把此结点 z 涂为黑色
• 情形 2: 如果当前结点的父结点是黑色，由于不违反性质 2 和性质 4，红黑树没有被破坏，所以此时也是什么也不做

比如上图插入 12 时满足情形 2:

以下情形需要作出额外调整:

• 情形 3: 如果当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色
• 情形 4: 当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置不在同侧
• 情形 5: 当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置在同侧

下面着重讲讲后三种情况如何调整

情形 3

当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色

因为当前节点的父节点是红色，所以父节点不可能是根节点，当前节点肯定有祖父节点，也就有叔叔节点

解决步骤: 将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，再把祖父结点当做新节点(即当前节点的指针指向祖父节点)重新检查各种情形进行调整
由于对称性，不管父结点是祖父结点的左子还是右子，当前结点是其父结点的左子还是右子，处理都是一样的
我们插入 21 这个元素，当前节点指向 21：

此时会发现 21、22 两个红色相连与性质 4 冲突，但 21 节点满足情形 3，修复后:

此时当前节点指向 21 的祖父节点，即 25。而 25 节点同样遇到情形 3 的问题，继续修复:

此时当前节点指向根节点，满足情形 1，将 14 节点涂黑即可恢复红黑树平衡

情形 4

当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置不在同侧
解决步骤:

• 如果当前节点是父节点的右子，父节点是祖父节点的左子，以当前结点的父结点做为新结点(即当前节点的指针指向父节点)，并作为支点左旋
• 如果当前节点是父节点的左子，父节点是祖父节点的右子，以当前结点的父结点做为新结点(即当前节点的指针指向父节点)，并作为支点右旋

在上图的基础上我们继续插入 5 这个元素:

可以看出 5 是父节点的左子，而父节点是祖父节点的右子，不同侧则为情形 4，将当前节点指向 5 的父节点 6，并以 6 为支点进行右旋:

此时当前节点是 6，而 6 是父节点 5 的右子，父节点 5 也是祖父节点 1 的右子，同侧则转为情形 5，继续往下看

情形 5

当前结点的父结点是红色，叔叔结点是黑色或者 nil，当前结点相对其父结点的位置和父节点相对祖父节点的位置在同侧
解决步骤:

• 首先把父结点变为黑色，祖父结点变为红色
• 如果当前节点是父节点的左子，父节点是祖父节点的左子，以祖父结点为支点右旋
• 如果当前节点是父节点的右子，父节点是祖父节点的右子，以祖父结点为支点左旋

在上一张图的基础上修改节点 5 为黑色，节点 1 为红色，再以 1 为支点左旋:

此时便恢复平衡

删除节点

删除节点 X 时第一步先判断两个孩子是否都是非空的，如果都非空，就先按二叉查找树的规则处理:
在删除带有两个非空子树的节点 X 的时候，我们可以找到左子树中的最大元素(或者右子树中的最小元素)，并把这个最值复制给 X 节点，只代替原来要删除的值，不改变节点颜色。
然后我们只要删除那个被复制出值的那个节点就行，因为是最值节点所以它的孩子不可能都非空。
因为只是复制了一个值，不违反任何性质，这就把原问题转化为如何删除最多有一个非空子树的节点的问题。它不关心这个节点是最初要删除的节点还是被复制出值的那个节点。
我们以图为例，图中三角形代表可能为空的子树:

节点 X 是要删除的节点，发现它的两个子树非空，我们可以找左子树中最大的元素 Max (也可以找右子树中最小的元素 Min)，把 Max 值(或者 Min 值)复制到 X 上覆盖原来的值，不修改其他属性，然后删除 Max 节点(或 Min 节点)即可，可以很清楚的看到最值节点最多只会有一个非空子树

接下来就是如何处理删除最多有一个非空子树的节点 X 的问题
简单情形:

1. 如果 X 的两个儿子都为空，即均为叶子，我们将其中任意一个看作它的儿子
2. 如果 X 是一个红色节点，它的父亲和儿子一定是黑色的，所以简单的用它的黑色儿子替换它就行，这并不会破坏性质 3 和性质 4，通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质 5
3. 如果 X 是黑色而它的儿子是红色，如果只是删除这个黑色节点，用它的红色儿子代替的话，会破坏性质 5，我们可以重绘它的儿子为黑色，则曾经通过 X 的所有路径将通过它的黑色儿子，这样可以继续保持性质 5

如果 X 和它的儿子都是黑色，这是一种复杂的情况，我们单拎出来讲
我们首先把要删除的节点 X 替换为它的儿子。出于方便，称呼这个新上位的儿子为 N，称呼它的兄弟为 S，使用 P 称呼 N 的新父亲，SL 称呼 S 的左儿子，SR 称呼 S 的右儿子
有以下六种情形需要考虑:

情形 1

N 是新的根
我们不需要做什么，因为所有路径都去除了一个黑色节点，而新根也是黑色的，所以性质都保持着

情形 2、5、6 涉及到左右不同的情况，只取一种处理

情形 2

S 是红色

• 交换兄弟 S 和父亲 P 的颜色
• 如果 N 是其父亲的左节点，我们在 N 的父亲上做左旋，把红色兄弟转换成 N 的祖父
• 如果 N 是其父亲的右节点，我们在 N 的父亲上做右旋，把红色兄弟转换成 N 的祖父

完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在 N 有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按情形 4、情形 5 或情形 6 来处理

情形 3

N 的父亲、S 和 S 的儿子都是黑色的

• 重绘 S 为红色
• 将 P 作为新的 N，从情形 1 开始，在 P 上做平衡处理

在这种情形下，我们简单的重绘 S 为红色。结果是通过 S 的所有路径都少了一个黑色节点。这与删除 N 的初始父亲 X 造成通过 N 的所有路径少了一个黑色节点达成平衡。但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反性质 5。要修正这个问题，我们要从情形 1 开始，在 P 上做重新平衡处理

情形 4

S 和 S 的儿子都是黑色，但是 N 的父亲是红色

• 交换 N 的兄弟 S 和父亲 P 的颜色

在这种情形下，我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过 N 的路径的黑色节点的数目，但是它在通过 N 的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点

情形 5

S 是黑色，S 的其中一个儿子是红色，且红色儿子的位置与 N 相对于父亲的位置处于同侧

• 如果 N 是其父亲的左节点，S 的左儿子是红色，右儿子是黑色，则在 S 上做右旋转
• 如果 N 是其父亲的右节点，S 的左儿子是黑色，右儿子是红色，则在 S 上做左旋转
• 将 S 和它之前的红色儿子交换颜色

所有路径仍有同样数目的黑色节点，但是现在 N 有了一个黑色兄弟，且兄弟的一个儿子仍为红色的，其位置与 N 相对于父亲的位置处于不同侧，进入情形 6

情形 5、6 中父节点 P 的颜色可以为黑色也可以是红色

情形 6

S 是黑色，S 的其中一个儿子是红色，且其位置与 N 相对于父亲的位置处于不同侧

• 交换 N 的父亲 P 和 S 的颜色
• 如果 N 是其父亲的右节点，S 的左儿子是红色，右儿子是黑色，则在 N 的父亲上做右旋转，并使 S 的左儿子涂黑
• 如果 N 是其父亲的左节点，S 的左儿子是黑色，右儿子是红色，则在 N 的父亲上做左旋转，并使 S 的右儿子涂黑

交换前 N 的父亲可以是红色也可以是黑色，交换后，N 增加了一个黑色祖先，所以通过 N 的路径都增加了一个黑色节点，S 的右子树黑色节点个数也没有变化，达到平衡

实例

还是以之前的图为例

我们自下而上开始尝试删除每一个节点:

• 假如要删除元素 1，根据简单情形中的第二条，我们直接删除 1，并用一个 nil 节点代替即可，元素 6、12、21 的处理与此相同
  
• 假如要删除元素 5，因为左右子树均不为空，所以找左子树的最大值 1 (或者右子树的最小值 6)，用找到的值代替 5 (这里只是值替换，其他均不变)，然后去删除 1 节点，这就转到问题 1 上了
  
• 假如要删除元素 11，根据简单情形的第三条，我们直接删除 11，并用子节点 12 代替，同时把 12 涂黑即可，元素 22 的处理与此相同
  
• 假如要删除元素 25，因为左右子树均不为空，所以找左子树的最大值 22 (或者右子树的最小值 27)，我们这里用值 22 代替 25，颜色不变。然后去删除 22 节点，这变成上一个问题了
  
• 假如要删除元素 27，黑色的 nil 叶子节点代替 27 节点，因为兄弟节点 22 有一个红色孩子，且在左边，和 nil 节点相对父亲 25 的位置不同侧，属于情形 6，所以第一步交换 22 和 25 的颜色，再以 25 为支点做右旋转，然后将 21 节点涂黑即可
  
• 假如要删除元素 8，选择右子树最小值 11 替换 8。然后去删除节点 11，对应问题 3
  
• 假如要删除元素 17，选择左子树最大值 15 替换 17。然后去删除节点 15，过程看下一个问题
  
• 假如要删除元素 15，删除的元素和替代的元素都是黑色，这属于复杂情形。检查其类型可以匹配到情形 2，元素 15 是被移除的 X，代替它的是 nil 节点，即为 N，17 为 P，25 为 S，根据上文可知第一步先交换 P 和 S 的颜色，然后以 P 为支点进行左旋，此时 N 多了一个黑色的兄弟 22 和红色的父亲 17:
  

此时 N 的兄弟 S 变为 22，P 变为 17，S 的左孩子是红色的 21，属于情形 5。S 做右旋转，并交换 22 和 21 的颜色:

此时 N 的兄弟 S 变为黑色的 21，但 21 的红色孩子节点 22 变为右侧，进入情形 6

P 节点 17 做左旋转，并将 S 的右节点涂黑，此时树恢复平衡

• 假如要删除根节点 14，取左子树最大值 12 代替 14。然后去删除节点 12，对应问题 1

至此，我们已经把节点都删了个遍，相信你对红黑树的删除操作应该了解了

红黑树动态展示: www.cs.usfca.edu/~galles/vis…

实际问题

红黑树还是典型的二叉搜索树结构，主要应用在一些 map 和 set 类型的实现上，比如 Java 中的 TreeMap 和 C++ 的 set/map/multimap 等。其查找的时间复杂度 与树的深度相关，降低树的深度可以提高查找效率。

Java 的 hashmap 和 golang 的 map 是用哈希实现的

但是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了）， 这样导致二叉查找树结构由于树的深度过大而造成磁盘 I/O 读写过于频繁，进而导致查询效率低下，因此我们该想办法降低树的深度，从而减少磁盘查找存取的次数。
一个基本的思想就是：采用多叉树结构，所以出现了下述的平衡多路查找树