Complete balancing via rotation

Fabrizio Luccio, Bernard Mans, Luke Mathieson*, Linda Pagli

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Trees are a fundamental structure in algorithmics. In this paper, we study the transformation of an arbitrary binary tree S with n vertices into a completely balanced tree T via rotations, a widely studied elementary tree operation. Combining concepts on rotation distance and data structures, we give a basic algorithm that performs the transformation in Θ(n) time and Θ(1) space, making at most 2n - 2 log2n rotations and improving on known previous results. The algorithm is then improved, exploiting particular properties of S. Finally, we show tighter upper bounds and obtain a close lower bound on the rotation distance between a zig-zag tree and a completely balanced tree. We also find the exact rotation distance of a particular almost balanced tree to a completely balanced tree, and thus show that their distance is quite large despite the similarity of the two trees.

Original languageEnglish
Pages (from-to)1252-1263
Number of pages12
JournalComputer Journal
Issue number8
Publication statusPublished - 1 Aug 2016


  • complete binary tree
  • design of algorithms
  • rotation distance
  • tree balancing


Dive into the research topics of 'Complete balancing via rotation'. Together they form a unique fingerprint.

Cite this