特点
AVL 树 (Adelson-Velsky and Landis Tree)：
- 规则： “绝对平衡”。它要求任何节点的左右子树高度差（平衡因子）最多为 1（即 -1, 0, 1）。
- 结果： 树的高度被压到最低，是一棵“矮胖”的二叉树。
红黑树 (Red-Black Tree)：
- 规则： “近似平衡”。它通过 5 条“红黑规则”（例如：节点非红即黑、根黑、叶黑、红色节点子必黑、黑高一致）来保证。
- 结果： 它不保证最低高度。它只保证最长路径（从根到最远叶子）不超过最短路径的两倍。
性能
这个“严格”与“宽松”的平衡策略，直接导致了它们在“增删”和“查找”上的性能权衡：
AVL 树
- 查找（Search）：更快。
- 原因：树更矮、更平衡。其 O(log N) 的常数因子是最小的。
- 增/删（Insert/Delete）：更慢。
- 原因：为了维持 |h_left - h_right| <= 1 这个苛刻的条件，它可能需要频繁地、自底向上地执行多次“旋转”（Rotation）操作，开销很大。
- 使用场景：“读多写少”的场景。例如：一个一经创建就不再修改的“数据字典”，或者查询频率远高于修改频率的系统。
红黑树 (RBT)
- 查找（Search）：稍慢。
- 原因：树可能“更高”一点（最多是 AVL 的两倍），O(log N) 的常数因子稍大。
- 增/删（Insert/Delete）：更快。
- 原因：它的平衡条件更宽松。
- 插入或删除时，它（在最坏情况下）只需要至多 2 次（插入）或 3 次（删除）旋转，更多时候是通过“变色”（Recoloring）（一个开销很小的操作）来重新满足红黑规则。
- 结论： RBT 在“增/删”操作上的“摊销”开销（Amortized Cost）远低于 AVL 树。
绝大多数的现实应用是“读写混合”的。std::map / std::set（C++）、Linux 内核调度器（CFS）… 它们都选择了红黑树。在这些场景中，“插入”和“删除”操作和“查找”一样频繁。红黑树通过牺牲一点点“查找”性能，换取了快得多的“增/删”性能，使得它的“综合性能”（Amortized Performance）在混合读写负载下是最优的。
红黑树/AVL树： 是内存数据结构。它们是二叉树，设计的前提是：内存访问（RAM）很快，CPU 比较（a < b）是主要开销。 B 树 / B+ 树： 是磁盘数据结构。它们不是二叉树，而是“多叉树”（M-ary Tree）。它们的设计前提是：磁盘 I/O 极慢（比内存慢 10 万倍），I/O 次数是唯一的性能瓶颈。