CODEWITHSUNDEEP
algorithmrotationbinary-search-tree
Ambroz Bizjak
Ambroz Bizjak

Reputation: 8095

Order rotation of a binary search tree

Suppose I have a balanced binary search tree representing this ordered sequence.

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

Given one of the elements, for example F, how do I efficiently transform the tree so that the result represents this ordered sequence?

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

The elements from F to the right were moved in front of all the other elements. Note that this has nothing to do with "tree rotation" in the usual sense. The rotation here happens in the sense of the order of the elements. It's the same as the meaning of "rotation" for a doubly linked list. For example, if the problem was about doubly linked lists and not binary search trees, the solution is trivial:

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

Is there an efficient solution for a balanced binary search tree?

Implementation note:

On first look it may seem that even if there was an efficient algorithm for this it would not be of much use, since the values of the moved elements would have to be updated to preserve the invariants of a binary search tree (left child is lesser, right child is greater). However, this is not the case, as in modular arithmetic modulo N, the order can be fixed in constant time without changing the values of the nodes. Suppose the order of the nodes is defined as folows:

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

Here, A.value, B.value and C are integers in the range [0,N). A graphical interpretation of this is that we have a circle with N points spread around, and we order the points such that C is the least point, followed by C+1, C+2, etc, up to C+(N-1), which is the greatest point.

Anyway, after moving F and all following elements to the front, the tree invariants can trivially be fixed by changing C:

C := F.value

Upvotes: 0

Views: 718

Answers (1)

comocomocomocomo
comocomocomocomo

Reputation: 4942

In general this can't be done in less than O(N) time. The balance can be recovered in O(log N) after a small change, but cutting a whole branch and pasting it somewhere else is a big change.

Extracting n elements and inserting them one by one would take O(n log N). If n is large, it's worth to rebuild the whole tree, which can be done in O(N) time.

That said, you can treat the whole sequence of the in-order traversal as a circular list. You might maintain a pointer to the element that you consider "the first", and just change it when you want to move some elements from "the end" to "the beginning", and vice versa. When you want to visit the sequence in order, just start with the pointed element ("the first"), continue the in-order traversal and wrap around the end of the tree. After visiting the rightmost element, continue with the leftmost. Stop when you reach "the first" element again.

Upvotes: 2

Related Questions