binary-search-tree - WAVL(弱AVL)和红黑树有什么区别？

Question

WAVL(弱AVL)和红黑树有什么区别？ 在 RB 上使用 WAVL 是否有特定原因？

Answer 1

WAVL 树是一种结合 AVL 树和红黑树的最佳特性的尝试。只需插入 WAVL 树就会构建与 AVL 树相同的树——比红黑树更严格平衡的树，因此可以预期 WAVL 树在红黑树变得更加不平衡的情况下表现更好。 WAVL 中的删除比 AVL 树的删除稍微简单一些，因为 WAVL 删除仅执行 1 或 2 次旋转并停止，而不是可能一直到根。