algorithm - 红黑树 - K 插入和 K 删除所需的最大旋转次数？

Question

红黑树K插入K删除后最多需要旋转多少圈？

我认为它是 3K，因为在插入的最坏情况下，我们为每次插入执行 2 次旋转，为每次删除执行 1 次旋转。我走在正确的轨道上吗？

Answer 1

与 AVL 树相比，删除的旋转可以传播到根(尽管插入最多有一个(双)旋转)，RB 树需要一个常量(插入最多 2 个，删除最多 3 个) ) 旋转次数。在 RB 树中删除期间可能花费对数级多的时间是可能传播到根的重新着色，这意味着插入和删除对于 AVL 和 RB 树具有相同的渐近线。

(有兴趣的可以找这些东西的分析in this script。)

关于您的问题，最多 3K 是正确的(但显然旋转的计数与链接脚本略有不同)。