1

将新元素插入n-element Red Black Tree 时的最大旋转次数是多少？

如果我是正确的，不违反 RBT 规则的插入需要最大2轮换（2 例）。假设是这样，O(1)也是正确答案吗？

如果是这样，请确认并告诉我，什么需要最多 3 次旋转？

4

1 回答 1

0

正确实现红黑树时最多需要 3 次操作（或 2 次旋转）。例如，此图中显示的中央 BST 将需要 3 次操作才能使其符合红黑 BST 的规则。

显示需要 3 次操作的情况的图像

图片取自此MOOC 中 Robert Sedgewick 的幻灯片。.

于 2014-03-21T12:55:37.540 回答