二叉排序树（BST）、平衡二叉树（AVL 树）、红黑树（Red-Black Tree）和 B 树（B-Tree）

1. 二叉排序树（Binary Search Tree, BST）

定义

• 二叉排序树是一种二叉树，满足以下性质：

  1. 左子树的所有节点值小于根节点。

  2. 右子树的所有节点值大于根节点。

  3. 左右子树也是二叉排序树。

特点

• 查找效率：

  • 平均时间复杂度：�(log⁡�)O(logn)。

  • 最坏情况（退化为链表）：�(�)O(n)。

• 插入和删除：

  • 平均时间复杂度：�(log⁡�)O(logn)。

  • 最坏情况：�(�)O(n)。

用途

• 适用于数据动态变化的场景，但需要避免退化为链表。

缺点

• 如果不平衡，性能会显著下降。

2. 平衡二叉树（AVL 树）

定义

• AVL 树是一种自平衡的二叉排序树，满足以下性质：

  1. 左右子树的高度差（平衡因子）不超过 1。

  2. 通过旋转操作（左旋、右旋）保持平衡。

特点

• 查找效率：

  • 时间复杂度：�(log⁡�)O(logn)。

• 插入和删除：

  • 时间复杂度：�(log⁡�)O(logn)。

  • 可能需要多次旋转来维持平衡。

用途

• 适用于需要频繁查找、插入和删除的场景，且对查询性能要求较高。

缺点

• 插入和删除时需要频繁调整平衡，开销较大。

3. 红黑树（Red-Black Tree）

定义

• 红黑树是一种自平衡的二叉排序树，满足以下性质：

  1. 每个节点是红色或黑色。

  2. 根节点是黑色。

  3. 每个叶子节点（NIL 节点）是黑色。

  4. 如果一个节点是红色，则它的两个子节点都是黑色。

  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

特点

• 查找效率：

  • 时间复杂度：�(log⁡�)O(logn)。

• 插入和删除：

  • 时间复杂度：�(log⁡�)O(logn)。

  • 通过颜色调整和旋转操作维持平衡。

用途

• 广泛应用于需要高效查找、插入和删除的场景，如：

  • C++ STL 中的 map 和 set。

  • Java 中的 TreeMap 和 TreeSet。

  • Linux 内核中的调度器和内存管理。

优点

• 相对于 AVL 树，红黑树的平衡条件更宽松，插入和删除的开销较小。

4. B 树（B-Tree）

定义

• B 树是一种多路平衡查找树，满足以下性质：

  1. 每个节点最多有 �m 个子节点（�m 阶 B 树）。

  2. 根节点至少有 2 个子节点（除非它是叶子节点）。

  3. 每个内部节点（非根和非叶子节点）至少有 ⌈�/2⌉⌈m/2⌉ 个子节点。

  4. 所有叶子节点位于同一层。

特点

• 查找效率：

  • 时间复杂度：�(log⁡�)O(logn)。

• 插入和删除：

  • 时间复杂度：�(log⁡�)O(logn)。

  • 通过节点分裂和合并维持平衡。

用途

• 适用于需要高效存储和访问大量数据的场景，如：

  • 数据库和文件系统的索引结构。

  • 磁盘存储系统（减少 I/O 操作）。

优点

• 适合存储在外存（如磁盘）中，因为节点可以存储多个键值，减少树的高度和 I/O 操作次数。

5. 对比总结

6. 实际应用场景

二叉排序树（BST）

• 适用于小规模数据或不需要严格平衡的场景。

• 例如：简单的字典或符号表。

平衡二叉树（AVL 树）

• 适用于对查询性能要求极高的场景。

• 例如：内存中的高效查找结构。

红黑树

• 适用于需要高效查找、插入和删除的场景。

• 例如：C++ STL 的 map 和 set，Java 的 TreeMap 和 TreeSet。

B 树

• 适用于需要存储大量数据并高效访问的场景。

• 例如：数据库索引、文件系统。