WAVL（弱AVL树）和红黑树有什么区别？

Question

WAVL（弱AVL树）和红黑树有什么区别？使用WAVL而不是RB是否有特定的原因？

- nadavs

---

你好，欢迎来到Stack Overflow。请注意，对于这个问题的回答可能会导致不完全基于事实或出于个人偏好而有所偏见的答案。也许在不同的使用情况下，每个选项都更适合用于特定的目的。如果想要得到关于这方面的答案，请考虑添加一些更多的细节到问题中，说明你想如何使用它以及为什么你觉得每个选项是否能够满足你的需求。希望你能找到适合自己的选项 :) - William Patton

Answer 1

WAVL树是将AVL树和红黑树的最佳特性结合在一起的尝试。只要将数据插入到WAVL树中，就会构建与AVL树相同的树 - 它比红黑树更加严格平衡，因此可以期望WAVL树在红黑树变得更不平衡的情况下表现更好。WAVL树中的删除比AVL树中的删除略微简单，因为WAVL删除只执行1或2次旋转并停止，而不是潜在地一直到根部。

- David McManamon

---

这话说起来很简单，但是网上没有任何解释 WAVL 树的内容，这使得我们无法验证他们算法的真实性。 - Eric Ouellet

我认为我们可以在网络上找到关于WAVL树的所有信息。您想要验证什么真相？有关它们的原始论文涵盖了所有细节，并且性能类似于Ben Pfaff 2004年论文中涵盖的AVL树（比红黑树快20%）。 - David McManamon

谢谢。我很想阅读原始的论文，详细解释所有规则。您还提到AVL比红黑树快20％。这对我来说听起来很奇怪，因为有许多变量可能会影响性能，例如使用递归或迭代，生成新节点的方式（从银行还是不从银行），您执行的操作：读取vs插入vs删除以及何时进行操作。这两个实现是否共享相同的优化。如果您有任何参考链接，包括在答案中将是不错的。似乎无法访问？ - Eric Ouellet

描述 WAVL 树的论文标题为“Rank Balanced Trees”，可在此处找到：http://sidsen.azurewebsites.net// Ben Pfaff 的论文在此处：https://benpfaff.org/papers/libavl.pdf。 - David McManamon