假设我有一个平衡的二进制搜索树来表示这个有序序列。
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
对于平衡的二进制搜索树，有没有一个有效的解决方案？
实施说明：
乍一看，即使有一种有效的算法，它也不会有多大用处，因为移动元素的值必须更新才能保留二进制搜索树的不变量（左子较小，右子较大）。然而，事实并非如此，因为在模运算中，阶数可以在恒定时间内固定，而不改变节点的值。假设节点的顺序定义如下：
(A < B) if and only if ((A.value - C) mod N) < ((B.value - C) mod N)
这里，A.value、B.value是[0，N）范围内的整数。对此的图形解释是，我们有一个圆形，其中N点分布在周围，我们对点进行排序，使C为最小点，然后是C+1，C++2等，直到C++（N-1） 无论如何，在将F和以下所有元素移动到前面之后，树不变量可以通过更改C来平凡地固定：C := F.value
通常情况下，这不能在少于O（N）的时间内完成。在一个小的变化后，平衡可以在O（log N）中恢复，但剪切整个分支并将其粘贴到其他地方是一个大的变化。
提取n个元素并逐个插入需要O（n log n）。如果n很大，那么重建整棵树是值得的，这可以在O（n）时间内完成。
也就是说，您可以将按顺序遍历的整个序列视为一个循环列表。您可以维护一个指向您认为是"第一个"的元素的指针，当您想将一些元素从"结束"移动到"开始"时，只需更改它，反之亦然。当您想按顺序访问序列时，只需从指向的元素（"第一个"）开始，继续按顺序遍历并环绕树的末尾。访问最右边的元素后，继续使用最左边的元素。再次到达"第一个"元素时停止。