极客教程红黑树和AVL树
在这篇文章中，我们将比较红黑树和 AVL 树。
红黑树：
特性
- 通过用一种两种颜色(红色或黑色)绘制每个节点来提供自平衡。
- 当树被修改时，新树随后被重新排列和重新绘制。
- 它需要树中每个节点的 1 位颜色信息。
红黑树维护的约束
- 根始终是黑色的。
- 所有 NULL 叶子都是黑色的，红色节点的两个孩子都是黑色的。
- 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。
- 从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。
AVL(Adelson-Velskii 和 Landis)树
特性：
- 节点左右子树的高度差应小于2。
- 当一个节点的两个子子树的高度相差一个以上时，就会进行重新平衡。
- 由于严格平衡，检索速度更快。
不同之处：
| 编号 | 没有红黑树 | AVL 树 |
|---|---|---|
| 1 | 红黑树的查找次数较少，因为它们不是严格平衡的。 | AVL 树比红黑树提供更快的查找，因为它们更严格地平衡。 |
| 2 | 在此，节点的颜色是红色或黑色。 | 在此，没有节点的颜色。 |
| 3 | 红黑树提供比 AVL 树更快的插入和删除操作，因为相对宽松的平衡，旋转更少。 | 由于相对宽松的平衡，AVL 树提供了复杂的插入和删除操作，因为进行了更多的旋转。 |
| 4 | 红黑树每个节点只需要 1 位信息。 | AVL 树存储每个节点的平衡因子或高度，因此每个节点需要存储一个整数。 |
| 5 | 它不提供有效的搜索。 | 它提供了高效的搜索。 |
| 6 | 红黑树用于大多数语言库，如 map、multimap、C++ 中的 multiset 等。 | AVL 树用于需要更快检索的数据库中。 |