The Rotation Graph of Binary Trees is Hamiltonian

Abstract:

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance binary search trees. It is a simple, local restructuring technique that alters the depths of some of the nodes in the binary tree. New binary search tree algorithms have recently been introducted by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees, which in turn will lead to a proof of this "dynamic optimality conjecture." We define a graph RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in O(C sub n) time, where each tree in the list differs from its predecessor by only one rotation.