The restricted rotation distance
d
R
(S, T) between two binary trees S, T of n vertices is the minimum number of rotations by which S can be transformed into T, where rotations can only take place at
the root of the tree, or at the right child of the root. A sharp upper bound d
R
(S, T) ≤ 4n – 8 is known, based on the word metric of Thompson’s group. We refine this bound to a sharp d
R
(S, T) ≤ 4n – 8 – ρS – ρT, where ρS and ρT are the numbers of vertices in the rightmost vertex chains of the two trees, by means of a very simple transformation algorithm
based on elementary properties of trees. We then generalize the concept of restricted rotation to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree. For k = 2 we show that not much is gained in the worst case, although the classical problem of rebalancing an AVL tree can be solved
efficiently, in particular rebalancing after vertex deletion requires O(log n) rotations as in the standard algorithm. Finding significant bounds and applications for k ≥ 3 is open.
Keywords Rotation - Rotation distance - Binary tree - Search tree - AVL tree - Rebalancing - Data structures - Design of algorithms