Amortized rotation cost in AVL trees

Mahdi Amani, Kevin A. Lai, Robert E. Tarjan

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

An AVL tree is a binary tree in which the heights of any two siblings differ by at most 1. Equivalently, it is a binary tree in which all height differences are 1 or 2. The authors Mahdi Amani, Kevin Lai and Robert Tarjan show that, for infinitely many n, there is a set E of expensive n-node AVL trees with the property that, given any tree in E, deleting a certain leaf and then reinserting it produces a tree in E, with the deletion having done rotations. They begin with some terminology. A node in a binary tree is binary, unary, or a leaf if it has two, one, or no children, respectively. A unary node or a leaf has one or two missing children, respectively. We define the depth of a node in a binary tree recursively as 1 plus the depth of its parent, or 0 if it is the root. Similarly, we define the height of a node in a binary tree as 1 plus the maximum of the heights of its children, or 0 if it is a leaf. To specify exactly how height information is updated and when rotations are done, they introduce node ranks AVL trees grow by leaf insertions and shrink by deletions of leaves and unary nodes. To add a leaf to an AVL tree, replace a missing node by the new leaf and give the new leaf a rank of 0. The authors show that any n-node AVL tree can be built from an empty tree by doing n insert.

Original languageEnglish (US)
Pages (from-to)327-330
Number of pages4
JournalInformation Processing Letters
Volume116
Issue number5
DOIs
StatePublished - 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • AVL tree
  • Data structures
  • Lower bound
  • Rotation

Fingerprint Dive into the research topics of 'Amortized rotation cost in AVL trees'. Together they form a unique fingerprint.

  • Cite this