红黑树vs AVL树

在这篇文章中，我们将比较红黑树和AVL树。

红黑树 :

属性 :

1. 通过给每个节点涂上一种或两种颜色（红色或黑色）来实现自平衡。
2. 当树被修改时，新树随后被重新排列和重新绘制。
3. 树中的每个节点都需要1位颜色信息。

约束条件 由红黑树维护 :

1. 根总是黑色的。
2. 所有空叶子都是黑色的，红色节点的两个子节点都是黑色的。
3. 从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色 节点。
4. 从根到最远叶片的路径不超过从根到最近叶片路径的两倍。

AVL（阿德尔森·维尔斯基和兰迪斯）树

属性 :

1. 节点左右子树的高差应小于2。
2. 当一个节点的两个子树的高度相差一个以上时，将进行重新平衡。
3. 更快的检索速度与严格平衡的检索速度一样快。

差别 :

1. AVL树提供 更快的查找 而不是红黑树，因为它们更严格地平衡。
2. 红黑树木提供 更快的插入和移除 与AVL树相比，由于相对放松的平衡，旋转次数更少。
3. AVL树木商店 平衡因子或高度 因此，对于每个节点，每个节点需要存储一个整数，而红黑树每个节点只需要1位信息。
4. 大多数语言库都使用红黑树，比如 地图 , 多重映射 , 多集 在C++中，而AVL树则用于 数据库 需要更快检索的地方。