声明：博文所有内容不是原创，是学习李明杰老师的腾讯课堂课程：《恋上数据结构与算法》后的总结。

树(Tree)的基本概念

兄弟节点：同一个父节点下的子节点互相叫做兄弟节点。

空数：一棵树没有任何节点

子树：父节点下的子节点为根节点所构成的树

左子树：父节点下的左子节点所构成的树，同理右子树

节点的度(degree)：子树的个数

树的度(degree)：所有节点度中的最大值

叶子节点(leaf)：度为0的节点，度不为0的叫非叶子节点

层数(lever)：根节点在第一层，根节点的子节点在第二层，以此类推

节点的深度(depth)：从根节点到当前节点的唯一路径上的节点总数，树的深度，所有节点深度中的最大值

节点的高度(height)：从当前节点到最远叶子节点的路径上的节点总数，树的高度，所有节点高度中的最大值

树的深度=树的高度

二叉树(Binary Tree)

特点：

每个节点的度最大为2.度只可能是 0，1，2
左子树和右子树是有顺序的(有序树)
即使某节点只有一颗子树，也要区分左右子树

性质：

非空二叉树的第 i 层，最多有 2^(i - 1) 个节点 (i >= 1)
在高度为 h 的二叉树上最多有 2^h - 1 个节点 (h >= 1)
对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为2的节点个数为 n2，则有 n0 = n2 + 1
- 2x = x + x/2 + x/4 +…+2+1 + 1

证明：
假设度为1的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
二叉树的边数 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

真二叉树

真二叉树：所有节点的度要么为0，要么为2，满二叉树：所有的叶子节点都在最后一层的真二叉树叫满二叉树

同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数最多，满二叉树一定是真二叉树，真二叉树不一定是满二叉树。

假设满二叉树的高度为 h (h >= 1)，那么

第 i 层的节点数量：2^(i - 1)
叶子节点数量：2^(h - 1)
总节点数量 n
- n = 2^h - 1
- h = log2(n + 1)

完全二叉树(complete Binary Tree)

叶子节点只会出现最后 2 层，且最后 1 层的叶子节点都靠左对齐，完全二叉树从根节点至倒数第二层是一颗满二叉树

度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为 h (h >= 1)，那么
- 至少有 2^(h - 1)次方个节点
- 最多有 2^h - 1 个节点
- 2^(h-1) <= n < 2^h
- h - 1 <= log2n < h，h = floor(log2n) + 1

floor(n) 向下取整， ceiling(n) 向上取整

有一颗有 n 个节点的完全二叉树 (n > 0)，从上到下、从左到右对节点 1 开始进行编号，对任意第 i 个节点

如果 i = 1，它是根节点
如果 i > 1，它的父节点编号为 floor(i / 2)
如果 2i <= n，它的左子节点编号为 2i
如果 2i > n，它无左子节点
如果 2i + 1 <= n，它的右子节点编号为 2i + 1
如果 2i + 1 > n，它无右子节点

有一颗有 n 个节点的完全二叉树 (n > 0)，从上到下、从左到右对节点 0 开始进行编号，对任意第 i 个节点

如果 i = 0，它是根节点
如果 i > 0，它的父节点编号为 floor((i - 1) / 2)
如果 2i + 1 <= n - 1，它的左子节点编号为 2i + 1
如果 2i + 1 > n - 1，它无左子节点
如果 2i + 2 <= n - 1，它的右子节点编号为 2i + 2
如果 2i + 1 > n，它无右子节点

面试题：如果一颗完全二叉树有768个节点，求叶子节点的个数
假设叶子节点个数为 n0，度为1的节点个数为 n1，度为2的节点个数为 n2，总节点个数为 n = n0 + n1 + n2，且 n0 = n2 + 1， n = 2n0 + n1 - 1，非叶子节点个数也是 n / 2
完全二叉树的 n1 要么为0，要么为1，因此，当 n1 为1时，n = 2n0，n 必然是偶数，n1 为 0 时， n = 2n0 - 1，n必然为奇数，n0 = (n + 1) / 2。非叶子节点个数是 (n - 1) / 2
通用公式：n0 = floor ((n + 1) / 2) 最终代码: n0 = (n + 1) >> 1 或者 (n >> 1) + 1

一些国外的说法

Full Binary Tree 完满二叉树，就是真二叉树，所有非叶子节点的度都为2
Perfect Binary Tree 完美二叉树，所有非叶子节点的度都为2，且所有叶子节点都在最后一层，即国内说的”满二叉树”
Complete Binary Tree 完全二叉树，跟国内定义一样

二叉搜索树 (Binary Search Tree)

思考
在 n 个动态的整数中搜索某个整数
假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度为 O(n)
如果使用的是有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)，但是添加删除的平均复杂度为 O(n)

针对上述需求，使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)

二叉搜索树是二叉树的一种，应用非常广泛的一种二叉树，英文简称 BST

又被称为：二叉查找树、二叉排序树

特点：

任意一个节点的值都大于它左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
二叉搜索树存储的元素必须具备可比较性
不允许为 null

二叉搜索树的接口设计

搜索二叉树需要实现的接口：

int size(); // 元素数量
boolean isEmpty() // 是否为空
void clear() // 清空所有元素
void add(E element) // 增加元素
void remove(E element) // 删除元素
boolean contains(E element) // 是否包含某元素

对于我们现在使用的二叉树来说，它的元素没有索引的概念

为什么？
添加顺序与元素大小无关。而且添加顺序与元素的层数也无关。

二叉搜索树的遍历

前序遍历 (Preorder Traversal)

根节点、前序遍历左子树、前序遍历右子树

递归

// 前序遍历
public void preorderTraversal(Node<E> node) {
    if (node == null) return;
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

迭代

中序遍历 (Inorder Traversal)

中序遍历左子树、根节点、右子树

二叉搜索树，中序遍历结果是升序或者降序的

后序遍历 (Postorder Traversal)

县访问左子树、再访问右子树、再访问根节点

层序遍历 (level Order Traversal) 需要会默写

实现思路：使用队列

将根节点入队
循环执行以下操作，直到队列为空
- 将队头节点 A 出队，进行访问。
- 将 A 的左节点入队
- 将 A 的右子节点入队

public void levelOrdertranversal() {
    if (root == null) return;
    
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        
        // 打印 node 节点的元素，这里写遍历要做的事
        
        if (node.left != null) {
            queue.offer(node.left);
        }
        
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

思考，如果允许外界遍历二叉树的元素，如何设计接口
采用给遍历方法，传递一个接口，接口的方法中放入业务代码的方式。内部当获取到遍历的元素时，调用对象的接口方法来操作元素。

前驱节点和后继节点

前驱节点 predecessor，指中序遍历时的前一个节点，根节点8的前驱节点是7。

求一个二叉树的前驱节点思路：

如果节点的左子树不为null
- predecessor = node.left.right.right…
- 终止条件为 right = null
如果节点的左子树为null，且节点的父节点不为空
- predecessor = node.parent.parent…
- 终止条件为 node.parent.right = node (node在parent的右子树中)
如果节点的左子树为null，节点的 parent 也为 null
- 没有前驱节点

后继节点 successor，中序遍历的后一个节点

如果 node.right != null
- successor = node.right.left.left…
- 终止条件：left = null
如果 node.right == null && node.parent != null
- successor = node.parent.parent…
- 终止条件 node.parent.left = node(node在parent的左子树中)
node.right == null && node.parent == null 没有后继节点

练习104：计算二叉树的高度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

递归：

public int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

迭代：层序遍历要知道一层有多少个

public int height() {
    if (root == null) return;
    
    int height = 0; // 存储树的高度
    int levelSize = 1; // 存储着每一层的元素数量，第一层的元素数量为1
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        // 每当取出一个元素，意味着每一层的元素数量--
        levelSize--;
        // 打印 node 节点的元素，这里写遍历要做的事
        
        if (node.left != null) {
            queue.offer(node.left);
        }
        
        if (node.right != null) {
            queue.offer(node.right);
        }
        
        if (levelSize == 0) { 
            // 意味着即将要访问下一层，所以队列中存储着下一层的所有元素，层数++ 
            levelSize = queue.size();
            height++;
        }
    }
}

练习：判断一棵树是否为完全二叉树

完全二叉树的叶子节点从上到下，从左到右排列。

思路：层序遍历，判断最高层数之前的每一层是否是满二叉树，
如果树为空，返回 false
如果树不为空，开始层序遍历二叉树(用队列)
如果node.left != null，&& node.right != null，将node.left 、 node.right 按顺序入队
如果node.left == null && node.right != null，返回false
如果node.left != null && node.right == null 或者 node.left == null && node.right == null 说明接下来所有节点都是叶子节点。如果有不是叶子节点的节点存在，则返回 false

/**
 * 是否为完全二叉树
 * @return
 */
public boolean isComplete() {
    if (root == null) return false;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) return false;
//      if (node.hasTwoChildren()) {
//          queue.offer(node.left);
//          queue.offer(node.right);
//      } else if (node.left == null && node.right != null) {
//          return false;
//      } else if (node.left != null && node.right == null) {
//          queue.offer(node.left);
//          leaf = true;
//      } else {
//          leaf = true;
//      }
        if (node.left != null) {
            queue.offer(node.left);
        } else if (node.right != null) {
            return false;
        }

        if (node.right != null) {
            queue.offer(node.right);
        } else {
            leaf = true;
        }
    }
    return true;
}

练习226：翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/

/**
 * 思路，将所有叶子节点的左右子树交换
 * 前序遍历节点
 *
 * @param root
 * @return
 */
public static TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    // 将节点的左右交换
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    invertTree(root.left);
    invertTree(root.right);

    return root;
}

练习114：二叉树展开为链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

flaten

public static void flatten(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) return;
    // 将左子树变为链表
    flatten(root.left);
    // 将右子树变为链表
    flatten(root.right);
    // 将右子树的链表拼接到左子树链表的末尾的右边
    TreeNode left = root.left;
    while (left != null) {
        TreeNode leftRight = left.right;
        if (leftRight == null) {
            left.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        left = leftRight;
    }
}

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

tree

解题思路：

ac050d257073f47285353d7ad412fb832326237ea85948a8b69d338171d67543-树的还原

练习105：从前序与中序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

练习889：根据前序和后序遍历构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

练习：寻找搜索二叉树的前驱节点(predecessor)和后继节点(successor)

概念：如果一颗二叉树存在左子树，其前驱节点是左子树最右边的节点。

若该节点存在右子树，则其后继节点为右子树最左边的节点

/**
 * 获取任意节点的前驱节点
 * @param node
 * @return
 */
public TreeNode predecessor(TreeNode node) {
    if (node == null) return null;
    TreeNode p = node.left;
    // 如果左子树不为空，前驱节点就是左子树中最右边的节点
    if (p != null) {
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    // 如果左子树为空，前驱节点就是父节点或者 node = node.parent.right 的时候的 parent
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }
    // 要么 node.parent == null，要么 node == node.parent.right
    return node.parent;
}

public TreeNode successor(TreeNode node) {
    if (node == null) return null;
    TreeNode p = node.right;
    if (p != null) {
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }
    return node.parent;
}

二叉搜索树的删除

分两种情况，分别为度为一或者零的节点、度为二的节点

private void remove(TreeNode node) {
    if (node == null) return;
    size--;
    // 度为2的节点
    if (node.hasTwoChildren()) {
        // 找到后继节点
        TreeNode<E> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.val = s.val;
        // 删除后继节点
        node = s;
    }
    // 删除node节点(node的度必然是1或者0)
    TreeNode<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {
        // node是度为1的节点
        // 将要接替node节点的节点replacement的parent指向node的parent
        // 此时，如果再将 node.parent的left或者right指向replacement，就完成了删除node节点的操作
        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.parent.right = replacement;
        }
    }
    // replacement == null 且 node.parent == null，说明node是叶子节点并且是根节点
    else if (node.parent == null) {
        root = null;
    } else {
        // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
    }
}

二叉搜索树的复杂度分析

添加，删除：比较次数跟树的高度有关，O(h) ==O(logn)，如果是满二叉树，高度的复杂度是 logn 级别的。

平衡二叉搜索树

平衡的概念：节点数量一定时，左右子树的高度越接近，二叉树就越平衡。(高度越低)

在节点的添加、删除之后，想办法让二叉搜索树恢复平衡，减少树的高度

AVL树

Windows NT 内核中广泛使用

平衡因子：某节点左右子树的高度差。

AVL树的特点：

每个节点的平衡因子只可能是1、0、-1(绝对值<=1，如果超过1，称为失衡)
每个节点的左右子树高度差不超过1
搜搜、添加、删除的时间复杂度是O(logn)

所以第二个二叉树是 AVL 树

添加节点

添加节点可能会导致所有祖先节点都失衡

只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡，仅需O(1)次调整

LL-右旋转（单旋）

左左，说明左边高度大，失衡，所以要右旋转

g.left = p.right

p.right = g

让p成为这颗子树的根节点。

还需要注意的是，T2、p、g的 parent 属性，更新 p 、g 的高度

RR-左旋转

g.right = p.left

p.left = g

让 p 成为这棵子树的根节点

LR-RR左旋转->LL右旋转(双旋)

RL-LL右旋转->RR左旋转(双旋)

删除节点

删除节会导致父节点或者祖先节点失衡(只有一个节点会失衡)，其他节点都不可能失衡，但是恢复平衡后，则可能导致更高层的祖先节点失衡，最多需要O(logn)次调整

如果删除一个节点，会导致父节点失衡，说明删除的是高度比较低的子节点，因此父节点的高度不会变化，所以除父节点外，都不会失衡

AVL树的平均时间复杂度

搜索：O(logn)

添加：O(logn)，需要O(1)次的旋转操作

删除：O(logn)，需要O(logn)次的旋转操作

B树

B树是一种平衡的多路搜索树，多叉树，用于文件系统、数据库实现。

1个节点可以存储超过2个元素，可以拥有超过2个子节点
拥有二叉搜索树的一些性质。
平衡，每个节点的所有子树高度一致

m阶B树的性质 m$\ge$2

$$
\begin{matrix}
一个树中节点最多拥有m个子节点，被称为m阶B树。\
假设一个节点存储的元素个数为x， \
若节点为根节点时，1\le x\le m-1，有子节点y：2\le y\le m。 \
若节点为非根节点，\lceil m/2\rceil -1 \le x\le m-1，有子节点y：\lceil m/2\rceil\le y \le m。\
比如：m=3，{\color{red}2}\le y\le{\color{red}3}，成为(2,3)树、2-3树 \
比如：m=4，{\color{red}2}\le y\le{\color{red}4}，成为(2,3)树、2-3-4树\
比如：m=5，{\color{red}3}\le y\le{\color{red}5}，成为(3,5)树 \
比如：m=6，{\color{red}3}\le y\le{\color{red}6}，成为(3,6)树 \
比如：m=7，{\color{red}4}\le y\le{\color{red}7}，成为(4,7)树 \
\end{matrix}
$$

2阶B树就是二叉搜索树

数据库底层数据存储结构用到了 B 树，一般是200-300阶B树

B树搜索

现在节点内部从小到大开始搜索元素
如果命中，搜索结束
如果没有，再去对应的子节点中搜索元素，重复步骤1

B树添加-例子为4阶B树

新添加的元素必定会添加到叶子节点

上溢：在m阶B树添加节点时，一个节点已经存在m-1个元素，添加时，超出了节点元素的最大值。叫做上溢。overflow

解决上溢问题：假设上溢节点中间位置的元素为k

将 k 位置的元素向上与父节点合并

将[0,k-1]和[k+1,m-1]位置的元素分裂成两个子节点，这两个子节点的元素个数，不会低于最低限制 $\lceil m/2 \rceil-1$。

一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决，

最极端的情况，一直分裂到根节点

B树删除-例子为5阶B树

删除的元素在叶子节点中，直接删除即可
- 删除30
删除的元素在非叶子节点中
- 先找到前驱或者后继元素，覆盖所需删除元素的值
- 再把前驱或者后继元素删除
- 删除 60
- 非叶子节点的前驱或者后继，必定在叶子节点中

下溢：叶子节点被删除一个元素后，元素个数可能会低于限制($\ge \lceil m/2\rceil -1$)

underflow

删除22 元素个数除根节点外，最低为5/2 -1= 2;

如果下溢节点临近的兄弟节点，至少有$\lceil m/2\rceil$个元素，可以向其借一个元素
- 将父节点 b 插入到下溢节点的头部(最小元素前面的位置)
- 用兄弟节点的尾部(最大元素)代替父节点的元素b
- 这种操作就是旋转：
- - 此处d，从a的右子节点转变为b的左子节点。原树中b > d > a
如果下溢节点临近的兄弟节点，只有$\lceil m/2\rceil-1$个元素
- 将父节点元素b下移和左右子节点合并
- 合并后，子节点元素个数=$\lceil m/2\rceil-1 + \lceil m/2\rceil-2 + 1 = 2 * \lceil m/2\rceil - 2$，不超过$m-1$。
- 这个操作有可能导致父节点下溢，依然按照上述方法解决，下溢现象会一直往上传播

红黑树

C++ STL(如 map、set)

Java 的 TreeMap、TreeSet、HashMap、HashSet

自平衡的二叉搜索树。

红黑树的特性

节点是 Red，或者 Black
根节点规定是 Black
叶子结点(所有的非空节点下，均为null节点，被称为叶子节点)，都是 Black
Red 节点的子节点一定是 Black
1. Red 节点的父节点一定是 Black
2. 从根节点到叶子节点所有路径上不会有两个连续的 Red
从任一节点到叶子节点的所有路径都包含数量相同的 Black 节点

红黑树的等价变换

红黑树和4阶B树 (2-3-4树)具有等价性

${\color{black}BLACK}$ 节点与它的 ${\color{red}RED}$ 子节点融合在一起，形成一个4阶B树节点
红黑树的 ${\color{black}BLACK}$ 节点个数与4阶B树的节点总数相等
网上有些教程：用2-3树与红黑树类比，是及其不严谨的，2-3树并不能完美匹配红黑树的的所有情况
后面展示的红黑树因空间有限，会省略 NULL 节点

parent 父节点，sibling 兄弟节点，uncle parent的兄弟节点

添加

已知：B树种新元素必定添加到叶子节点中

在红黑树添加节点会出现的所有情况如下示例：

建议新添加的节点默认为 Red，这样的好处是，可以在添加节点后，依然满足性质1、2、3、5，性质4不一定满足。

以下是添加节点时所有的情况：

如果添加的是根节点，染成 ${\color{black}BLACK}$ 即可。
上述包含了所有可能出现的情况中，一共有12种节点添加位置的情况。其中4种是满足红黑树性质4的：即 parent 为 ${\color{black}BLACK}$
- 此时不用做额外处理，同时有8种情况不满足红黑树的性质4： ${\color{red}RED}$ 的parent一定是 ${\color{black}BLACK}$
前4种属于B树节点上溢
- 判定条件：uncle 节点是 ${\color{red}RED}$ ，解决方案如下：
- 将添加节点的 parent、uncle 染成 ${\color{black}BLACK}$ ，并且把 grand 染成 ${\color{red}RED}$ ，然后当做新添加的节点向上合并。重复添加逻辑。示例如下：
其他类型为 LL/LR/RL/RR 型
- 判定条件：uncle 不是 ${\color{red}RED}$ ，其中 LL/RR型解决方案如下：
- 将添加节点的 parent 染成 ${\color{black}BLACK}$ ，grand 染成 ${\color{red}RED}$ ，对 grand 进行单旋操作，其中LL型是图最右边添加的节点，grand节点右旋转，RR型是图中靠左的节点，grand节点左旋转
- LR/RL型解决方案如下：
- 将添加的节点染成 ${\color{black}BLACK}$ ，grand 染成 ${\color{red}RED}$ ，进行双旋操作，其中LR型是图中最右的节点，parent 左旋转，然后 grand 右旋转。RL型是图中靠左的节点，parent 右旋转，然后 grand 左旋转。

删除

在B树种，最后真正被删除的元素都在叶子节点中，具体情况有以下几种

直接删除 ${\color{red}RED}$ 节点，不用做任何调整
删除拥有2个 ${\color{red}RED}$ 节点的 ${\color{black}BLACK}$ ，比如图中的25，由于 BinarySearchTree 的特性，会将其前驱或者后继节点的值赋给图中25节点的位置，所以图中25节点不会被直接删除，因此不用考虑该情况。
拥有1个 ${\color{red}RED}$ 子节点的 ${\color{black}BLACK}$ 节点
- 如果度为1，找到 ${\color{red}RED}$ 取代他，判定条件：用以替代的子节点是 ${\color{red}RED}$ ，解决方案：将代替的子节点染成 ${\color{black}BLACK}$ 即可保持红黑树性质。
- 如果度为0，判定条件：用以替代的子节点是 ${\color{black}BLACK}$ ，这种情况是比较复杂的，因为会导致B树节点下溢，比如删除88
  - 第一种情况，sibling是 ${\color{black}BLACK}$
    - sibling至少有一个 ${\color{red}RED}$ 子节点。
      - 此时，应该进行旋转操作，图一，删除88，变为LR，先对76左旋，然后对80右旋。图二，删除88，变为LL，对76进行右旋。图三中，删除88后，既可以看成 80,76,78的LR型，也可以看成 80,76,72的LL型，这里为了方便，当成LL型，即对80节点进行右旋转即可。
      - 图一与图二、图三的判断依据：图一的sibling.left是null，也就是sibling.left是 ${\color{black}BLACK}$
      - 旋转之后，中心节点应改为删除节点parent 的颜色，左右节点染色 ${\color{black}BLACK}$ 。
    - sibling没有一个 ${\color{red}RED}$ 子节点。
      - 图一情况：parent 是 ${\color{red}RED}$ ，将 sibling 染色 ${\color{red}RED}$ ，将 parent 染色 ${\color{black}BLACK}$ 。也就是4阶B树的节点下溢。
      - 图二情况：parent 是 ${\color{black}BLACK}$ ，会导致 grand 下溢，这时，只需要把 parent 当做被删除的节点处理即可（递归）。
  - 第二种情况，sibling是 ${\color{red}RED}$
    - 思路：想办法让 sibling（55）变成 ${\color{black}BLACK}$ ，将parent（80）右旋，将 sibling（55）染成 ${\color{black}BLACK}$ ，parent（80）染成 ${\color{red}RED}$ 。
    - 就变成了 sibling 为 ${\color{black}BLACK}$ 的情况，按照之前的情况处理：

思考：代码中的afterRemove方法，可以只传一个参数

具体做法，把 replacement 参数删除，然后再度为1的时候，不传node，传replacement即可。

private void remove(TreeNode node) {
    if (node == null) return;
    size--;
    // 度为2的节点
    if (node.hasTwoChildren()) {
        // 找到后继节点
        TreeNode<E> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.val = s.val;
        // 删除后继节点，
        node = s;
    }
    // 删除node节点(node的度必然是1或者0)
    TreeNode<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {
        // node是度为1的节点
        // 将要接替node节点的节点replacement的parent指向node的parent
        // 此时，如果再将 node.parent的left或者right指向replacement，就完成了删除node节点的操作
        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.parent.right = replacement;
        }
        // 删除节点之后的调整
        afterRemove(replacement);              // <-----这里改一下
    }
    // replacement == null 且 node.parent == null，说明node是叶子节点并且是根节点
    else if (node.parent == null) {
        root = null;
        // 删除节点之后的调整
        afterRemove(node);
    } else {
        // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
        // 删除节点之后的调整
        afterRemove(node);
    }
}

在红黑树中，将

// 如果要删除的节点是红色，什么也不做
if (isRed(node)) return;

// 如果删除的是黑色且度为1的节点，用子节点替代，子节点必然是红色，将其染色黑色即可
if (isRed(replacement)) {
    black(replacement);
    return;
}

这段代码合并

// 如果删除的是黑色且度为1的节点，用子节点替代，子节点必然是红色，将其染色黑色即可
// 如果删除的是叶子节点，且为红色，染黑再删除
if (isRed(replacement)) {
    black(replacement);
    return;
}

程序运行结果不会改变。

代码仓库