8.BST的缺陷解决方案：平衡树*****

目录

1. AVL树

1.1 性质

1.2 具体实现细节

大概如何实现的逻辑：

怎样平衡：

1.3 性能

2. 红黑树

2.1 性质

2.2 具体实现细节

怎样平衡：

2.3 性能

3. AVL 与 RBT 的区别

1. AVL树

1.1 性质

AVL树也叫“高度平衡二叉搜索树”：

• 它的左右子树都是AVL树
• 左右子树高度之差(平衡因子)的绝对值不超过1

1.2 具体实现细节

2. AVL树-CSDN博客

大概如何实现的逻辑：

AVL树是一种自平衡二叉搜索树，通过维护每个节点的平衡因子（左右子树高度差不超过1）来确保树的平衡。其核心实现包括

• 每个节点包含键值、左右子节点指针和高度信息。

• 平衡因子 = 左子树高度 - 右子树高度，必须为 -1、0 或 1。

  • 按二叉搜索树规则插入节点。

  • 更新节点高度。

  • 检查平衡因子，若失衡则通过旋转恢复平衡。

怎样平衡：

根据插入结点后，父节点的平衡因子的大小，以及新插入的节点的位置，进行平衡操作。

• 父节点的平衡因子 = 0，平衡，不用向上更新
• -1 / 1，有点小病，问题不大，需要向上更新
• -2 / 2，失衡，需要根据插入结点的位置选择旋转方式
  • 右右-左单旋
  • 右左-右左双旋
  • 左左-右单旋
  • 左右-左右双旋

1.3 性能

        AVL树是一棵绝对平衡的二叉搜索树，这可以保证查询时高效的时间复杂度 O(logN) 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时因为要维护绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

        因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(不增不减)，可以考虑AVL树，但一个结构经常修改的话就不太合适。

2. 红黑树

2.1 性质

        红黑树也是一种BST，但在每个结点上增加一个存储位标识结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此是接近平衡的。

• 每个结点是 红色 或 黑色
• 根结点是 黑色
• 叶子节点（空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），那些null节点才是叶子节点
• 红色节点的孩子都是黑色
  • 红色节点的父亲都是黑色
  • 从根到NULL结点的所有路径上不能有 2 个连续的红色节点
• 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

2.2 具体实现细节

3. 红黑树-CSDN博客

怎样平衡：

插入的框架和AVL树类似，不同处出现在旋转的判断：

        由于新插入的节点默认为红色，若它的父亲为黑色，直接插入就行；如果它的父亲为红色，此时父与子都是红色，违反了“不能有两个连续红色节点”的规则，需要进行处理：

        由于我们需要知道新节点的uncle的信息，所以要分左右：

• 如果 p(parent) 在 g(grandfather) 的 左，那么 u(uncle) 就在 g 的右
• 如果 p(parent) 在 g(grandfather) 的 右，那么 u(uncle) 就在 g 的左

上面两种情况都有各自的处理方式：

第一种：p 在 g 的左，u 在 g 的右：

• 如果u存在且为红色，此时 p 和 u 和 cur 为红色，此时最长路径的长度没有超过最短二倍：
  • 把 p 和 u 变黑，g 变红，此时继续向上更新，c = g，p = c→_parent：
    • 若 g 没有父亲，就是根，g变回黑即可
    • g 有父亲，且父亲为黑色，结束
    • g 有父亲，且父亲为红色，此时又出现了两个连续节点为红的情况，判断p 在 g的左还是右，就变成了上面分左右的两种情况
• 如果 u 不存在 或 u 为黑，此时 cur 为红，p 是红，此时最长路径的长度超过最短的二倍，单纯的变色无法解决问题，需要根据新增节点在p的左/右分情况进行旋转+变色：
  • 如果 c 在 p 的左，此时由于 p 在 g 左，g、p、c 构成 左左-右单旋
    • RotateR(grandfather)，p 由红变黑，g 由黑变红
  • 如果 c 在 p 的右，此时由于 p 在 g 左，三个节点构成 左右-左右双旋
    • RotateL(parent)-折线变直线，RotateR(grandfather)-直线变三角，cur 由红变黑，g由黑变红

第二种：p 在 g 的右，u 在 g 的左：

• 如果u存在且为红色，此时 p 和 u 和 c是红色，此时最长路径的长度没有超过最短二倍：
  • 把 p 和 u 变黑，g 变红，此时继续向上更新，c = g，p = c→_parent：
    • 若 g 没有父亲，就是根，g变回黑即可
    • g 有父亲，且父亲为黑色，结束
    • g 有父亲，且父亲为红色，此时又出现了两个连续节点为红的情况，判断p 在 g的左还是右，就变成了上面分左右的两种情况
• 如果 u 不存在 或 u 为黑，此时 cur 为红，p 是红，此时最长路径的长度超过最短的二倍，单纯的变色无法解决问题，需要根据新增节点在p的左/右分情况进行旋转+变色：
  • 如果 c 在 p 的右，此时由于 p 在 g 右，g、p、c 构成 右右-左单旋
    • RotateL(grandfather)，p 由红变黑，g 由黑变红
  • 如果 c 在 p 的左，此时由于 p 在 g 右，三个节点构成 右左-右左双旋
    • RotateR(parent)-折线变直线，RotateL(grandfather)-直线变三角，cur 由红变黑，g由黑变红

我们可以总结出规律：红黑树插入关键看uncle：

        如果 uncle 存在且为红，不管uncle在gradfather的左还是右，这种只需要变色的情况，两种情况变色的过程是相同的。

        如果 uncle 不存在 或 存在且为黑，此时两种情况也只是因为 parent 相对于 grandfather 的左或右(因为 cur 在 parent 的左或右这两种情况都会出现，所以不影响)，在旋转方式上有所不同，但他们的节点变色过程是一样的。

2.3 性能

        红黑树的核心操作（查找、插入、删除）的时间复杂度均为 O(log n)。红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的两倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树的实现比较简单，所以实际运用中红黑树更多。

3. AVL 与 RBT 的区别