AVL 树的“删除”操作在实践中最坏的情况是什么样的？

Question

我找到了这个堆栈溢出答案：https://stackoverflow.com/a/28846533/10061169，这表明AVL树“删除”操作可以有O（log（N））旋转。我目前正在尝试通过构建一个示例来找到该声明的证据。我发现了这个：https://cs.stackexchange.com/questions/128245/worst-case-for-avl-tree-balancing-after-deletion。然而，在相应示例中，当删除节点“19”时，将执行 2 次旋转。这甚至不接近 Log(N)。该示例的 Log(N) 将为 Log(20) = 4.3。

我自己做了一些更多的研究，了解如何构建 AVL 树，该树在删除单个节点时会给出 O(log(n)) 旋转。这是我找到的结构：

删除节点“25”将导致 AVL 树执行以下旋转：

1. 向左旋转
2. 右旋转
3. 向左旋转
4. 右旋转

取 log(n)，得到 log(12) = 3.6，它（如果向上舍入）与 4 次旋转对齐。这证明了堆栈溢出答案中的陈述：https://stackoverflow.com/a/28846533/10061169。

这就是 AVL 树“删除”操作在实践中最坏的情况吗？还是还有更多有待发现？

Answer 1

引用的答案正确识别了最坏的情况。

你这样写：

...将执行 2 次旋转。这甚至不接近 Log(N)。该示例的 Log(N) 将为 Log(20) = 4.3。

但是Big O不能这样比较。大 O 涉及渐近复杂度，因此 O(log𝑛) = O(log𝑛 / 10) = O(1000 log𝑛)。

您已经确定了另一个示例，其中两个重新平衡操作都是 double 轮换。但因子 2 与渐近复杂度无关。同样，O(log𝑛) 等于 O(2log𝑛) 等于 O(log𝑛 / 2)。