高度差：描述是某一节点的左右子树的高度差。即等于左子树层数 - 右子树层数。

平衡二叉树/平衡二叉搜索树（BBST）：树中任一节点左右子树的高度相差不超过 1 的树。

BST

性质

二叉搜索树是一种非常直观的二叉树结构，它满足以下四个基本特性：

每个节点都有一个关键值（Key），并且所有节点的关键值互不相同。
左子树上所有节点的关键值都小于该节点的关键值。
右子树上所有节点的关键值都大于该节点的关键值。
左、右子树也分别为二叉搜索树。

这使得中序遍历（in-order）会产生有序序列（升序）。

理想情况

BST的核心优势在于其搜索效率。如果树的结构是平衡的（左右子树的高度相差不大），那么每次比较都能排除掉大约一半的数据。这时，搜索、插入、删除的时间复杂度都是 O(log n)，非常高效。

搜索：从根节点开始，比当前节点小就往左走，大就往右走，等于就找到。
插入：先执行搜索，找到应该插入的位置（一个空子树），然后挂上新节点。
删除：核心思想是：找到要删除节点后，用其左子树的最大节点或右子树的最小节点来替代它。

现实情况

BST的性能严重依赖于树的“平衡度”。

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，树完全不平衡，高度为n。

所有操作的时间复杂度将从 O(log n)劣化为 O(n)。

AVL

AVL树又称为自平衡二叉搜索树（self-BBST）。

性质

它满足以下五个基本特性：

每个节点都有一个关键值（Key），并且所有节点的关键值互不相同。
左子树上所有节点的关键值都小于该节点的关键值。
右子树上所有节点的关键值都大于该节点的关键值。
左、右子树也分别为AVL树。
对于树中的任意一个节点，其左子树的高度和右子树的高度之差的绝对值不超过1。这个差值被称为平衡因子。（平衡因子的取值只有1，0，-1）

在插入、删除树节点的时候，如果破坏了以上的原则，AVL树会自动进行调整使得以上五条性质仍然成立。

插入节点

/* 插入节点 */
public void insert(int val) {
    //传入的是root节点，这是关键
    //意味着每一次插入/删除，从底层直到根节点，都会更新高度、尝试旋转
    root = insertHelper(root, val);
}

/* 插入节点委托方法 */
//递归地处理
private TreeNode insertHelper(TreeNode node, int val) {
    if (node == null){
        //node为空，说明遍历到叶子节点了，可以插入新节点了
        //这里返回一个节点，在1处，该节点就会被设定为左子节点/右子节点
        return new TreeNode(val);
    }
    /* 1. 查找插入位置并插入节点 */
    if (val < node.val)
        //return 回来，设定为left-sub
        node.left = insertHelper(node.left, val);
    else if (val > node.val)
        //return 回来，设定为right-sub
        node.right = insertHelper(node.right, val);
    else
        // 找到值一样的节点，不插入，直接返回
        // 注意：这里返回node，会被设定为左子节点/右子节点，但是本来就是，再设定也没效果
        return node; 
    
    //这里是后序位置 插入节点完成
    // 更新节点高度
    updateHeight(node); 
    /* 2. 尝试执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 注意：这里返回node，会被设定为左子节点/右子节点
    // 如果继续了旋转，这个node会是新的子节点
    return node;
}

删除节点

/* 删除节点 */
public void remove(int val) {
    //传入的是root节点，这是关键
    //意味着每一次插入/删除，从底层直到根节点，都会更新高度、尝试旋转
    root = removeHelper(root, val);
}
/* 递归删除节点 委托方法*/
private TreeNode removeHelper(TreeNode node, int val) {
    if (node == null)
        return null;
    /* 1. 查找节点并删除 */
    if (val < node.val)
        node.left = removeHelper(node.left, val);
    else if (val > node.val)
        node.right = removeHelper(node.right, val);
    else {
        //找到值相等的，要删除的节点了
        if (node.left == null || node.right == null) {
            TreeNode child = node.left != null ? node.left : node.right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == null)
                return null;
            // 子节点数量 = 1 ，直接删除 node
            else
                node = child;
        } else {
            // 子节点数量 = 2
            // 找到要删除节点的右子树中最小的节点（中序后继）
            // （为什么是右子树：一定比要删除节点的值大）
            // （为什么是最小节点：一定不比要删除的节点大得多）
            TreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            // 2. 删除这个中序后继节点
            // 为什么不直接写成removeHelper(temp, temp.val);
            // 因为要考虑：删除中序后继节点后，右子树全部都要更新高度、尝试旋转
            node.right = removeHelper(node.right, temp.val);
            // 把中序后继节点的值直接覆盖到当前节点，完成“删除”，减少操作
            node.val = temp.val;
        }
    }
    // 后序位置
    // 删除后，更新当前节点高度
    updateHeight(node); 
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点，便于父节点设置
    return node;
}

调整类型

调整的关键

确定最底层的失衡节点node，以失衡节点node的子节点child作为支点pivot，进行旋转。

/* 获取平衡因子 */
int balanceFactor(TreeNode node) {
    // 空节点平衡因子为 0
    if (node == null)
        return 0;
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node.left) - height(node.right);
}

一棵 AVL 树的任意节点的平衡因子皆满足 −1≤ factor ≤1 。

否则，这个节点可以认定为失衡节点，AVL树需要进行调整。

右旋

插入的节点，在根节点左侧子树，且插入的节点在父节点左侧。LL型失衡节点——右旋。

找到最底层（离叶子节点近的）的失衡节点node。

(注意，旋转操作一般发生在插入、删除的后序，意味着是从底向上的进行调整失衡)
node的左子节点为child，以child作为支点pivot（只有node以左子节点child作为支点旋转，成为child右子节点，才是右旋），
child右子节点指向node，
如果child还有右子节点grand_child，node左子节点接上grand_child。
返回child节点，被设定为新的子树根节点/总根节点。

/* 右旋操作 */
private TreeNode rightRotate(TreeNode node) {
    TreeNode child = node.left;
    TreeNode grandChild = child.right;
    // 以 child 为原点，将 node 向右旋转
    child.right = node;
    //grandC 代替 child的位置
    node.left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

右旋携带子节点图示

左旋

插入的节点，在根节点右侧子树，且插入的节点在父节点右侧。RR型失衡节点——左旋。

找到最底层（离叶子节点近的）的失衡节点node。

(注意，旋转操作一般发生在插入、删除的后序，意味着是从底向上的进行调整失衡)
node的右子节点为child，以child作为支点pivot（只有node以右子节点child作为支点旋转，成为child左子节点，才是左旋），
child左子节点指向node，
如果child还有左子节点grand_child，node右子节点接上grand_child。
返回child节点，被设定为新的子树根节点/总根节点。

//左旋
private TreeNode leftRotate(TreeNode node){
    TreeNode child = node.right;
    TreeNode grandChild = child.left;
    
    child.left = node;
    //child在node right
    //那么grandChild 必然大于 node
    //那么grandC 就得接到 node right上 
    //或者说 grandC 代替 child的位置
    node.right = grandChild;
    
    updateHeight(node);
    updateHeight(child);
    
    return child;
}

先左旋，再右旋

插入的节点，在根节点左侧子树，且插入的节点在父节点右侧。LR型失衡节点——先失衡节点左子左旋，再失衡节点右旋。

node.left = leftRotate(node.left);
rightRotate(node);

先右旋，再左旋

插入的节点，在根节点右侧子树，且插入的节点在父节点左侧。RL型失衡节点——先失衡节点右子右旋，再失衡节点左旋。

node.right = rightRotate(node.right);
leftRotate(node);

旋转方法

/* 执行旋转操作，使该子树重新恢复平衡 */
private TreeNode rotate(TreeNode node) {
    // 获取节点 node 的平衡因子
    int balanceFactor = balanceFactor(node);
    // 左偏树 /（偏左，要往右掉）
    if (balanceFactor > 1) {
        //左偏树 子左偏 LL = R旋
        if (balanceFactor(node.left) >= 0) {
            // 右旋，返回child 新子树根节点，给insert/remove方法设置
            return rightRotate(node);
        } else {
            //左偏树 子右偏 LR = LR旋

            // 先左子左旋，返回值设置给当前失衡节点左子
            // 后右旋
            node.left = leftRotate(node.left);
            // 返回child 新子树根节点，给insert/remove方法设置
            return rightRotate(node);
        }
    }
    // 右偏树 \（偏右，要往左掉）
    if (balanceFactor < -1) {
        // RR = L旋
        if (balanceFactor(node.right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // RL = RL旋

            // 先右旋后左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}

RBTree红黑树

由于AVL树必须保证左右子树平衡。

所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。

正是由于这种严格的平衡条件，导致AVL需要花大量时间在调整上，故AVL树一般使用场景在于查询场景，而不是 插入、删除频繁的场景。

红黑树继承了AVL可自平衡的优点，

同时, 红黑树在查询速率和平衡调整中寻找平衡，放宽了树的平衡条件，从而可以用于 插入、删除频繁的场景。

在实际应用中，红黑树的使用要多得多。

性质

红黑树通过为每个节点增加一个颜色属性（红色或黑色）并遵循以下五条规则来定义：

节点是红色或黑色。
根节点是黑色。
所有叶子节点（NIL节点，空节点）都是黑色。
红色节点的两个子节点都必须是黑色。（即：不能有两个连续的红色节点）
从任意节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

规则4和规则5共同保证了，从根节点到最远叶子节点的路径长度（黑节点数量相同，但红节点数量不同）不会超过最短路径长度的两倍。这保证了树是“大致平衡”的，高度始终在 log n 的数量级上。

插入场景

默认：**要插入节点初始化为红色。**除非进行调整变色，否则插入节点默认是红色。

因为父节点为黑色的概率较大，插入新节点为红色，可以避免颜色冲突。

红黑树为空树

直接插入，根据红黑树性质 2根节点是黑色的，还需要把插入节点设置为黑色。

插入节点的Key已经存在

更新已插入节点的值，不插入新节点。

插入节点的父节点为黑色

由于插入的节点是默认是红色，当插入节点的父节点是黑色时，不会影响红黑树的平衡。

所以： 直接插入，红黑树无需调整。

插入节点的父节点为红色

N：当前节点（新插入的节点，或递归向上检查的节点）。
P：N的父节点。
U：N的叔父节点（P的兄弟节点）。
G：N的祖父节点（P和U的父节点）。

根据：

性质2：根节点是黑色。

性质4：不能有两个连续的红色节点

因此：

如果P为红色节点，那么P不可能为根节点，所以P为红色节点，必然存在G节点(三代关系)，且G是黑色节点。（平衡状态下）

此时会出现两种状态（由于插入节点的父节点为红色）：

P、U都为红色
P为红色，U为黑色

父亲P和叔叔U，都为红色

此时 G 必定是黑色，因为规则4在插入前是满足的。

由于插入的新节点默认为红色，除非进行调整。

性质4：不能有两个连续的红色节点

新节点插入后，需要进行调整。

处理策略： 变色

操作步骤：

将父节点 P 和叔父节点 U 变为黑色。
将祖父节点 G 变为红色。
将当前节点 N 指向 G（即把 G 当作新插入的节点，递归向上检查和处理）。

      黑(G)                   红(G)  <-- (新的N，因为可能引发问题，需要处理)
      /    \                  /    \
   红(P)   红(U)   -->     黑(P)   黑(U)
    /                      /
 红(N)                   红(N)

父亲P为红色，叔叔U为黑色

P 是红色，U 是黑色（或是NIL空节点，默认为黑）。

P 是 G 的左孩子，N 是 P 的左孩子（左左）；对应AVL的LL失衡。
P是 G 的右孩子，N 是 P 的右孩子（右右）。对应AVL的RR失衡。
P 是 G 的左孩子，N 是 P 的右孩子（左右）；对应AVL的LR失衡。
P 是 G 的右孩子，N是P的左孩子（右左）。对应AVL的RL失衡。

P 是 G 的左孩子，N 是 P 的左孩子

左左操作步骤：

处理策略：对 G 进行右旋 + P/G交换颜色

对祖父节点 G 进行一次右旋。（记G为失衡节点node，P为child）
将父节点 P 的颜色与祖父节点 G 的颜色进行交换。（不会产生双红）
- 旋转后，P 成为了新的子树根。
- P 变为 G 原来的颜色（通常是黑色）。
- G 变为红色。

爷爷变爸爸，爸爸变爷爷。

解释（左左）：
旋转操作将P提升到了G的位置，N仍然在P的左侧。通过交换颜色，我们保证了新的子树根P是黑色（不会与上层产生双红），并且修复了N和P的双红问题。路径上的黑色节点数量保持不变。

 初始状态（违反规则4：P和N都是红色）: 

	   黑(G)
      /    \ 
   红(P)   黑(U)
    /
 红(N)
步骤1：记G为失衡节点`node`，P为`child`，对G进行右旋得到

      红(P)
     /    \
   红(N)   黑(G)
          	 \
            黑(U)
步骤2：交换P和G的颜色
           
     黑(P)
    /    \
  红(N)   红(G)
           \
           黑(U)

处理完成后，整棵子树的黑高平衡，且不再有双红，调整结束。

P 是 G 的右孩子，N 是 P 的右孩子

右右操作步骤

处理策略：对 G 进行左旋 + P/G交换颜色

解释：

初始状态（违反规则4：P和N都是红色）:

      黑(G)
      /    \
   黑(U)   红(P)
            \
            红(N)
步骤1：记G为失衡节点`node`，P为`child`，对G进行左旋得到
          
        红(P)
        /    \
      黑(G)  红(N)
      /
    黑(U)
步骤2：交换P和G的颜色
          
        黑(P)                    <-- 新的子树根，黑色保证不产生新问题
        /    \
      红(G)  红(N)
      /
    黑(U)

P 是 G 的左孩子，N 是 P 的右孩子

左右操作步骤

处理策略：对P进行左旋，对G进行右旋，N/G交换颜色

操作步骤：

对父节点 P 进行一次左旋（将折线型转为直线型）
此时变成了左左情况，按情况1处理：对 G 进行右旋，并交换 N 和 G 的颜色

初始状态（违反规则4：P和N都是红色）:

      黑(G)
      /    \
   红(P)   黑(U)
      \
      红(N)
步骤1：以P作为失衡节点，进行左旋得到（将折线转为直线）
          
      黑(G)
      /    \
   红(N)   黑(U)
    /
  红(P)
步骤2：现在变成了左左情况。以G作为失衡节点，进行右旋得到
          
        红(N)   <-- 新的子树根
        /    \    
      红(P)  黑(G)
      		   \
   			  黑(U) 
步骤3：N/G交换颜色
          
        黑(N)
        /    \    
      红(P)  红(G)
      		   \
   			  黑(U)

P 是 G 的右孩子，N 是 P 的左孩子

右左操作步骤

处理策略：对P进行右旋，对G进行左旋，N/G交换颜色

操作步骤：

对父节点 P 进行一次右旋（将折线型转为直线型）
此时变成了右右情况，按情况2处理：对 G 进行左旋，并交换 N 和 G 的颜色

初始状态（违反规则4：P和N都是红色）:

      黑(G)
      /    \
   黑(U)   红(P)
          /
        红(N)
步骤1：以P作为失衡节点，进行右旋得到（将折线转为直线）
          
      黑(G)
      /    \
   黑(U)   红(N)
          	\
        	红(P)
步骤2：现在变成了右右情况。以G作为失衡节点，进行左旋得到
          
        红(N)   <-- 新的子树根
        /    \    
      黑(G)  红(P)
      / 
   黑(U) 
          
步骤3：N/G交换颜色
         黑(N)
        /    \
      红(G)  红(P)
      /
    黑(U)

调整算法

如果 N 是根节点？
- 是：将 N 变为黑色，结束。
- 否：进入下一步。
父节点 P 是黑色？
- 是：没有违反任何规则，结束。
- 否：进入下一步（出现了“双红”，需要修复）。
进入核心情况判断：
- 情况一：如果叔父节点 U 是红色。
  - 操作：P 和 U 变黑，G 变红，然后递归向上处理 G。
- 情况二/三：如果叔父节点 U 是黑色（或NIL）。
  - 判断 N 与 P 的位置关系：
    - 情况二（直线型）：如果 (N 是 P 的左孩子且 P 是 G 的左孩子) 或 (N 是 P 的右孩子且 P 是 G 的右孩子)。
      - 操作：对 G 进行一次旋转（左左则右旋，右右则左旋），并交换 P 与 G 的颜色。
    - 情况三（折线型）：如果 (N 是 P 的右孩子且 P 是 G 的左孩子) 或 (N 是 P 的左孩子且 P 是 G 的右孩子)。
      - 操作：先对 P 进行一次旋转（左右则对P左旋，右左则对P右旋），将其转化为情况二，然后按情况二处理。

删除场景

//TODO

参考

https://www.cnblogs.com/crazymakercircle/p/16320430.html

https://github.com/krahets/hello-algo/blob/main/codes/java/chapter_tree/avl_tree.java

https://www.hello-algo.com/chapter_tree/avl_tree/

Grinofith's Blog

BST、AVL、红黑树

BST

性质

理想情况

现实情况

AVL

性质

插入节点

删除节点

调整类型

调整的关键

右旋

右旋携带子节点图示

左旋

先左旋，再右旋

先右旋，再左旋

旋转方法

RBTree红黑树

性质

插入场景

红黑树为空树

插入节点的Key已经存在

插入节点的父节点为黑色

插入节点的父节点为红色

父亲P和叔叔U，都为红色

父亲P为红色，叔叔U为黑色

P 是 G 的左孩子，N 是 P 的左孩子

P 是 G 的右孩子，N 是 P 的右孩子

P 是 G 的左孩子，N 是 P 的右孩子

P 是 G 的右孩子，N 是 P 的左孩子

调整算法

删除场景

参考

JVM 笔记