C++八股——平衡树总结

1. 定义

平衡树（Balanced Tree）是一种自平衡的二叉搜索树（Binary Search Tree，BST），通过某种机制保持树的高度尽可能低，从而确保查找、插入和删除操作的时间复杂度维持在$O(logn)$

BST：当前节点左子树中的任何一个节点的权值均严格小于当前节点的权值，右子树中的任何一个节点的权值均严格大于当前节点的权值。其中序遍历的结果是从小到大的有序序列。

2. 各种平衡树

2.1 AVL树

• 平衡机制：通过旋转（左旋/右旋）保持左右子树高度差不超过1。
• 性质：
  • 严格的平衡性，树高始终为 $O(logn)$。
  • 插入/删除可能需要多次旋转。
• 时间复杂度：
  • 查找、插入、删除：$O(logn)$。
• 应用场景：
  • 需要频繁查询但对插入/删除效率要求不高的场景（如内存数据库）。

2.2 红黑树（Red-Black Tree）

• 平衡机制：通过颜色标记和旋转约束树的平衡。
  • 规则：
    1. 根节点为黑色。
    2. 红色节点的子节点必须为黑色。
    3. 任意路径到叶子节点的黑色节点数相同（叶子节点为NULL，且为黑色，一般省略）。
• 性质：
  • 近似平衡，树高至多为 $2log(n+1)$。
  • 插入/删除最多需要 3 次旋转。
• 时间复杂度：
  • 查找、插入、删除：$O(logn)$。
• 应用场景：
  • 需要高效动态操作的场景（如 C++ STL 的 map/set、Java TreeMap）。
• 参考：
  • 【C++】——红黑树（手撕红黑树，彻底弄懂红黑树）_c++ 红黑树-CSDN博客
  • （数据结构）如何手搓一棵红黑树（RedBlack-Tree）_手搓红黑树-CSDN博客
  • 红黑树图文简洁解析-CSDN博客
  • c++手撕代码 (一) 红黑树 - 知乎

2.3 B树（B-Tree）

• 平衡机制：通过节点分裂/合并维护多路平衡。
  • 每个节点最多包含 $m-1$ 个键和 $m$ 个子节点（$m$ 为阶数）。
• 性质：
  • 多叉树结构，减少磁盘 I/O 次数。
  • 所有叶子节点在同一层。
• 时间复杂度：
  • 查找、插入、删除：$O(logn)$。
• 应用场景：
  • 文件系统和数据库索引（如 MySQL 的 InnoDB 存储引擎）。

2.4 B+树（B+ Tree）

• 衡机制：类似 B 树，但叶子节点通过指针形成有序链表。
• 性质：
  • 数据仅存储在叶子节点，内部节点只存键。
  • 支持高效的范围查询和顺序遍历。
• 时间复杂度：
  • 查找、插入、删除：$O(logn)$。
• 应用场景：
  • 数据库索引（如 Oracle、PostgreSQL）、文件系统（NTFS）。

2.5 伸展树（Splay Tree）

• 平衡机制：通过伸展操作（将最近访问的节点移动到根附近）实现局部性优化。
• 性质：
  • 无严格平衡性，但访问频率高的节点靠近根。
  • 摊还时间复杂度为 $O(logn)$。
• 应用场景：
  • 缓存优化、数据局部性强的场景（如网络路由表）。

2.6 Treap

• 平衡机制：结合二叉搜索树（BST）和堆（Heap）特性，节点包含随机优先级。
• 性质：
  • 以 BST 的键顺序和堆的优先级维护平衡。
  • 期望高度为 $O(logn)$。
• 应用场景：
  • 随机化算法、需要简单实现的平衡树（如竞赛编程）。
• 实现：C++数据结构 —— 平衡树Treap-CSDN博客

2.7 替罪羊树（Scapegoat Tree）

• 平衡机制：检测不平衡子树并重构（暴力重建）。
• 性质：
  • 无旋转操作，通过重构子树保持平衡。
  • 查找效率严格 $O(logn)$。
• 应用场景：
  • 需要避免旋转操作的场景（如嵌入式系统）。

2.8 2-3树 / 2-3-4树

• 平衡机制：节点可包含 2 或 3 个子节点（2-3树）或 2/3/4 个子节点（2-3-4树）。
• 性质：
  • 所有叶子节点在同一层。
  • 插入/删除通过节点分裂/合并维护平衡。
• 应用场景：
  • B 树的前身，用于理论教学和内存受限系统。

2.9 AA树（AA-Tree）

• 平衡机制：红黑树的简化版本，仅用“层次”标记替代颜色。
• 性质：
  • 插入/删除仅需单旋转或双旋转。
  • 代码实现简单。
• 应用场景：
  • 需要红黑树功能但追求代码简洁的场景。

2.10 加权平衡树（Weight-Balanced Tree）

• 平衡机制：通过子树权重（节点数）比例约束平衡。
• 性质：
  • 子树权重比不超过预设阈值（如 3:1）。
  • 适合动态数据分布场景。
• 应用场景：
  • 数据分布不均匀时的动态维护（如几何计算）。

总结对比

平衡树类型	核心平衡机制	严格平衡性	适用场景
AVL树	高度差约束 + 旋转	严格	高频查询场景
红黑树	颜色标记 + 旋转	近似	综合读写场景（STL容器）
B树/B+树	多路节点分裂/合并	严格	磁盘存储与数据库索引
伸展树	局部性伸展操作	无	缓存优化
Treap	随机优先级堆	概率平衡	简单随机化实现
替罪羊树	不平衡子树重构	严格	避免旋转操作的系统