algorithm - 二叉搜索树的顺序旋转

Question

假设我有一个代表这个有序序列的平衡二叉搜索树。

A<B<C<D<E<F<G<H

给定其中一个元素，例如 F，我如何有效地转换树以使结果表示这个有序序列？

F<G<H<A<B<C<D<E?

从 F 到右边的元素被移动到所有其他元素的前面。请注意，这与通常意义上的“树旋转”无关。这里的旋转发生在元素顺序的意义上。这与双向链表的“旋转”含义相同。例如，如果问题是关于双向链表而不是二叉搜索树，则解决方案很简单:

E.next := null
F.prev := null
H.next := A
A.prev := H

平衡二叉搜索树是否有有效的解决方案？

实现说明:

乍一看，即使有一个有效的算法，它也没有多大用处，因为移动元素的值必须更新以保留二叉搜索树的不变量(左 child 较小，右 child 较大)。然而，情况并非如此，因为在模块化算术模 N 中，可以在常数时间内固定顺序而不更改节点的值。假设节点的顺序定义如下:

(A < B) if and only if ((A.value - C) mod N) < ((B.value - C) mod N)

这里，A.value、B.value 和C 是 [0,N) 范围内的整数em>。对此的图形解释是，我们有一个由 N 个点分布的圆，我们对这些点进行排序，使得 C 是最少的点，其次是 C +1、C+2 等，直到 C+(N-1)，这是最重要的一点。

无论如何，在将 F 和所有后续元素移到前面后，可以通过更改 C 轻松修复树不变量:

C := F.value

Answer 1

一般来说，这不能在少于 O(N) 的时间内完成。一个小改动后可以在 O(log N) 中恢复平衡，但是剪切整个分支并将其粘贴到其他地方是一个很大的改动。

提取 n 个元素并将它们一个接一个地插入将花费 O(n log N)。如果 n 很大，则值得重建整棵树，这可以在 O(N) 时间内完成。

也就是说，您可以将中序遍历的整个序列视为一个循环列表。您可能会维护一个指向您认为是“第一个”的元素的指针，并在您想要将某些元素从“结尾”移动到“开头”时更改它，反之亦然。当你想按顺序访问序列时，只需从指向的元素(“第一个”)开始，继续中序遍历并绕到树的末端。访问最右边的元素后，继续访问最左边的元素。再次到达“第一个”元素时停止。