二叉搜索树（BST）、AVL树、红黑树

下面

我们来详细讲解一下二叉搜索树（BST）、AVL树和红黑树这三种经典的树形数据结构。它们都是用来高效地存储和检索有序数据的，但在平衡性、性能和实现复杂度上各有侧重。

一、二叉搜索树

1. 定义与性质

二叉搜索树是最基础的树形结构，它必须满足以下性质：

1. 左子树的所有节点值均小于根节点的值。
2. 右子树的所有节点值均大于根节点的值。
3. 左、右子树也分别是二叉搜索树。
4. 没有键值相等的节点。（通常定义如此）

示例：

      8/ \3   10/ \    \1   6    14/ \   /4   7 13

2. 操作与时间复杂度

• 查找： 从根节点开始，比较目标值与当前节点值。如果目标值小，则去左子树查找；如果大，则去右子树查找。直到找到目标或到达空节点。
• 插入： 类似查找，找到合适的空位（叶子节点）进行插入。
• 删除： 比较复杂，分三种情况：
  1. 删除叶子节点： 直接删除。
  2. 删除只有一个子节点的节点： 用其子节点替换它。
  3. 删除有两个子节点的节点： 找到其中序后继（右子树的最小值）或中序前驱（左子树的最大值），用该节点的值替换要删除的节点，然后删除那个后继/前驱节点（它必然是情况1或2）。

理想情况下的时间复杂度：O(log n)
当树是完全平衡或接近平衡时，树的高度为 log n，所有操作都只需沿着从根到叶的一条路径进行。

最坏情况下的时间复杂度：O(n)
如果插入的序列是有序的（例如，1, 2, 3, 4, 5），BST会退化成一个链表。

1\2\3\4

在这种情况下，树的高度为 n，所有操作都退化为线性查找，性能急剧下降。

3. 优缺点

• 优点：
  • 结构简单，易于理解和实现。
  • 在数据随机分布时，性能良好。
  • 支持中序遍历，可以方便地得到有序序列。
• 缺点：
  • 无法自平衡。 在极端数据（有序或逆序）下会退化成链表，性能无法保证。

二、AVL树

1. 定义与性质

AVL树是最早被发明的自平衡二叉搜索树。它通过一个严格的平衡条件来确保树永远不会退化。

• 性质1： 它首先是一棵二叉搜索树。
• 性质2： 平衡因子： 对于树中的任意一个节点，其左子树的高度与右子树的高度的差的绝对值不能超过1。这个差值就是平衡因子。
  • Balance Factor = Height(Left Subtree) - Height(Right Subtree)
  • AVL树中所有节点的平衡因子只能是 -1、0 或 1。

示例：

      8 (BF=0)/ \(BF=0)3   10 (BF=-1)/ \    \
(BF=0)1   6 (BF=0) 14 (BF=0)/ \   /
(BF=0)4   7 (BF=0)13 (BF=0)

这棵树每个节点的BF都在[-1, 1]之间，所以是AVL树。

2. 平衡机制：旋转

当插入或删除操作导致某个节点的平衡因子变为 +2 或 -2 时，AVL树会通过旋转操作来恢复平衡。旋转分为四种情况：

1. 左-左情况： 在节点的左子树的左子树上插入导致不平衡。执行右旋。
2. 右-右情况： 在节点的右子树的右子树上插入导致不平衡。执行左旋。
3. 左-右情况： 在节点的左子树的右子树上插入导致不平衡。先对左子节点左旋，再对当前节点右旋。
4. 右-左情况： 在节点的右子树的左子树上插入导致不平衡。先对右子节点右旋，再对当前节点左旋。

每次插入或删除后，都需要从操作点向上回溯，检查并修复所有祖先节点的平衡性。

3. 操作与时间复杂度

• 查找、插入、删除： 由于树始终保持高度平衡，其高度稳定在 O(log n)。虽然插入和删除可能需要多次旋转，但旋转操作是常数时间的，所以总的时间复杂度仍为 O(log n)。

4. 优缺点

• 优点：
  • 严格的平衡性。 查找性能非常稳定，始终是 O(log n)，是三种树中查找效率最高的。
• 缺点：
  • 维护成本高。 每次插入和删除都可能引发多次旋转，需要频繁地更新节点的高度和平衡因子。
  • 删除操作尤其复杂。 删除后可能需要一直回溯到根节点进行平衡调整。

三、红黑树

1. 定义与性质

红黑树是另一种自平衡二叉搜索树，但它采用了比AVL树更宽松的平衡标准，用颜色和规则来保证大致的平衡。

• 性质1： 每个节点要么是红色，要么是黑色。
• 性质2： 根节点是黑色。
• 性质3： 所有叶子节点都是黑色的空节点。
• 性质4： 没有两个相邻的红色节点。（即一个红色节点的子节点必须是黑色的）。
• 性质5： 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这个数目被称为该节点的“黑高”。

示例：

      (B)8/   \(R)3   (B)10/   \     \(B)1   (B)6   (R)14/   \   /(R)4  (R)7 (B)13

这棵树满足所有红黑树的性质。

2. 平衡机制：旋转与重新着色

红黑树的平衡操作比AVL树更复杂，涉及旋转和重新着色。当插入或删除破坏了红黑树的性质时（主要是性质4和5），通过以下操作来修复：

1. 重新着色： 改变节点颜色（红变黑，黑变红）。
2. 旋转： 和AVL树一样，包括左旋、右旋。

插入和删除的修复逻辑有固定的“套路”，通过分析叔叔节点的颜色来决定下一步操作是旋转还是重新着色。

3. 操作与时间复杂度

• 查找、插入、删除： 红黑树的平衡是“大致平衡”，其最长路径不会超过最短路径的两倍。因此，树的高度也保持在 O(log n) 级别。所以，所有操作的时间复杂度也是 O(log n)。

4. 优缺点

• 优点：
  • 插入和删除效率更高。 由于平衡标准更宽松，插入和删除操作引发的旋转次数通常比AVL树少。对于需要频繁插入和删除的场景，性能更好。
  • 实现虽然复杂，但模式化。 修复逻辑虽然绕，但有固定的规则可循。
• 缺点：
  • 查找性能略逊于AVL树。 因为树的高度可能比AVL树稍高，所以查找路径可能更长，但仍在O(log n)级别。

三者对比总结

如何选择？

• 如果你需要实现一个简单的有序数据结构，并且数据是随机插入的，或者数据量不大，那么普通的BST就足够了。
• 如果你的应用是“读多写少”，比如一个字典、一个需要频繁查询但不常修改的索引，那么AVL树是更好的选择，因为它能提供最稳定、最快的查询速度。
• 如果你的应用是“写多读少”，或者读写操作都很频繁，比如操作系统任务调度（CFS）、C++的std::map/std::set、Java的TreeMap/TreeSet等，那么红黑树是更优的选择。它在插入和删除上的高效性，使得整体性能更加均衡和出色。