平衡二叉树

平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

AVL树

AVL树是高度平衡的二叉树。它的特点是: AVL树中任何节点的两个子树的高度最大差别为1。

节点插入

当插入节点导致二叉树失去平衡时，可以概括为4个状态：

• LL：表示高度失衡节点的左子树的左孩子导致左子树比右子树高度大2，AVL树失去平衡；
• LR：表示高度失衡节点的左子树的右孩子导致左子树比右子树高度大2，AVL树失去平衡；
• RR：表示高度失衡节点的右子树的右孩子导致右子树比左子树高度大2，AVL树失去平衡；
• RL：表示高度失衡节点的右子树的左孩子导致右子树比左子树高度大2，AVL树失去平衡。

当AVL树发生上述4中失衡时，需要对应使用4种类型旋转，调整AVL树，使其重新保持平衡状态：

• LL单旋：树往右单旋

  

• RR单旋：树往左单旋

  

• LR双旋：先左子树RR单旋，然后整棵树LL单旋

  

• RL双旋：先右子树LL单旋，然后整棵树RR单旋

  

节点删除

AVL树删除节点的过程是，先找到该节点，然后进行删除。由于删除节点的位置不同，导致删除后节点进行移动的方式不同。删除节点的位置分为以下4类：

1. 叶子节点：直接删除即可，然后依次向上调整为AVL树
2. 只有左孩子的非叶子节点：该节点值替换为左孩子节点，删除左孩子，然后依次向上调整为AVL树
3. 只有右孩子的非叶子节点：该节点值替换为右孩子节点，删除右孩子，然后依次向上调整为AVL树
4. 有左右孩子的非叶子节点：该节点的值替换前驱（左孩子）节点，删除前驱节点（最终状态变成1、2、3中的一个）。

红黑树

红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。 它必须满足下面性质：

1. 根节点是黑色的；
2. 每个节点非红即黑；
3. 所有叶子节点都是（NIL），为黑色；
4. 如果1个节点红色的，那么它的两个子节点就是黑色的，即没有连续红节点；
5. 任意节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点。

节点插入

红黑树插入节点时需要遵循以下原则：

1. 插入的结点一定是红色的，如果为黑色，会破坏性质5；
2. 如果插入的是根节点，将颜色改为黑色；
3. 如果插入节点的父节点是黑色，则插入完成；
4. 如果插入节点的父节点是红色，则需要修复，且继续向上调整，直到为根或满足规则；
5. 如果根修改之后为红色，一定要改成黑色。

因此，插入节点时最复杂的操作就是出现“红红”时（上述第4条）怎么修复红黑树。

修复方法

• 前提条件： 插入的结点（cur）是红色，cur的父结点（parent）是红色的，这样的需要修复。

• 修复要点： 保证修复操作前和修复操作后的黑色结点的数量不变。

• 可推断出： cur 的祖父结点即父亲的父亲（grandpa）一定是黑色，否则插入当前结点之前已经违反了红黑树的规则

  

• 下面对cur节点的uncle节点进行分情况讨论

  • 情况1：uncle存在，并且uncle的颜色是红色

    修复方法：grandpa 由黑变红，parent & uncle 由红变黑 。如下图所示：

    

  • 情况2：uncle不存在，或者uncle存在但是颜色为黑色**

    • 情况2.1：cur是parent的左孩子，且parent是grandpa的左孩子

      修复方法： grandpa 右旋之后颜色变为红色，parent 的颜色变为黑色。如下图所示：

      

    • 情况2.2：cur是parent的右孩子，且parent是grandpa的右孩子**

      修复方法：grandpa 左旋后颜色变为红色，parent 颜色变为黑色。如下图所示：

      

    • 情况2.3：cur是parent的右孩子，且parent是grandpa的左孩子

      修复方法：对 parent 左旋之后将 parent 和 cur 的名称交换，再按照2.1的情况处理。如下图所示：

      

    • 情况2.4：cur是parent的左孩子，且parent是grandpa的右孩子

      修复方法：对 parent 右旋之后将 parent 和 cur 的名称交换，再按照2.2的情况处理。如下图所示：

      

节点删除

和AVL树类似，红黑树删除节点也分三种情况：

1. 删除节点为叶子节点
   • 节点为红色：无需修复，不会破坏红黑树任何性质。
   • 节点为黑色：需要修复，破坏红黑树性质5。
2. 删除节点为非叶子节点
   • 有1个子节点：将删除节点与子节点值交换，删除子节点，此时情况转变成第1种（删除叶子节点）
   • 有2个子节点：将删除节点值与其后继节点值（前驱也可以）交换，删除后继节点，此时有一下两种情况：
     • 后继节点是叶子节点：情况转变成第1种
     • 后继节点有1个子节点：情况变成第2种下的第1种
     • 后继节点有2个子节点：情况变成第2种下的第2种

可以发现删除的所有情况最终都可以转变成第1种。在第1种情况下，节点为红色时无需修复，节点为黑色是需要修复，因此我们只需要关注这一种情况即可。

修复方法

• 前提条件：删除节点为叶子节点，且颜色为黑色

• 修复要点：保证修复操作前和修复操作后的黑色结点的数量不变。

• 可推断出：被删除节点一定有兄弟节点

• 修复：下面对兄弟节点的颜色分情况讨论（下图中所有黑色方框null表示被删除节点）

  • 情况1：兄弟节点为黑色

    • 情况1.1：兄弟节点为黑色，且有一个与其方向一致的红色子节点

      

    • 情况1.2：兄弟节点为黑色，且有一个与其方向不一致的红色子节点

      

    • 情况1.3：兄弟节点为黑色，且没有红色子节点（也不可能有黑色子节点，否则原红黑树不平衡）

      

  • 情况2：兄弟节点为红色，则其父节点必为黑色（否则红红相连）

    

    图(i)中将brother和father旋转，重新上色后，变成了图(j)，新的brother（原来的son）变成了黑色，这样就变成了情况1。

参考资料

1. https://blog.csdn.net/qq_21388535/article/details/105601270

2. https://blog.csdn.net/jinking01/article/details/106020347

3. https://pdai.tech/md/algorithm/alg-basic-tree-balance.html

4. https://blog.csdn.net/qq_40843865/article/details/102498310