Complete balancing via rotation

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

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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
Volume59
Issue number8
DOIs
Publication statusPublished - 1 Aug 2016

Keywords

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

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

  • Cite this

    Luccio, F., Mans, B., Mathieson, L., & Pagli, L. (2016). Complete balancing via rotation. Computer Journal, 59(8), 1252-1263. https://doi.org/10.1093/comjnl/bxw018