AVL树与WAVL树在增删查操作中节点秩修改次数对比探究

咱们先设定一个场景：从空树出发，对AVL树和WAVL树执行完全相同的插入、删除及搜索操作序列。现在要搞清楚的核心问题是：这两种树的节点秩修改次数到底是相同的，还是呈常数倍关系？

我得说，这个“次数相同或呈常数倍”的结论是不成立的，咱们可以通过一个具体的操作序列来分析：

• 假设操作序列的总长度为n，先执行n/2次插入操作：在这个阶段，AVL树和WAVL树的节点秩修改次数大致相近。毕竟插入操作主要是维护树的平衡特性，两者的旋转调整逻辑虽然有差异，但对于大部分常规插入场景，需要修改秩的节点数量差距并不大。
• 但当进入后续的删除操作阶段时，两者的差异会开始显现。WAVL树的平衡规则允许节点之间有更大的秩差，在某些删除场景下，需要调整秩的节点数量会远少于AVL树；而在另一些极端场景下，情况可能反转，这就导致两者的秩修改次数差距不再是固定的常数倍，甚至会随着n的增大而被不断放大。

内容的提问来源于stack exchange，提问作者Vitaly G