0

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

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

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

实施说明：

乍一看，即使有一个有效的算法，它也没有多大用处，因为必须更新移动元素的值以保留二叉搜索树的不变量（左孩子较小，右孩子更大）。但是，情况并非如此，因为在模算术模N中，顺序可以在恒定时间内固定，而无需更改节点的值。假设节点的顺序定义如下：

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

这里，A.value、B.value和C是[0,N)范围内的整数。对此的图形解释是，我们有一个散布有N个点的圆，我们对这些点进行排序，使得C是最小的点，然后是C+1、C+2等，直到C+(N-1)，这是最大的一点。

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

C := F.value
4

1 回答 1

2

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

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

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

于 2013-02-26T06:50:19.223 回答