Rank-balanced trees

Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Since the invention of AVL trees in 1962, a wide variety of ways to balance binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We introduce the rank-balanced tree, a relaxation of AVL trees. Rank-balanced trees can be rebalanced bottom-up after an insertion or deletion in O(1) amortized time and at most two rotations worst-case, in contrast to red-black trees, which need up to three rotations per deletion. Rebalancing can also be done top-down with fixed lookahead in O(1) amortized time. Using a novel analysis that relies on an exponential potential function, we show that both bottom-up and top-down rebalancing modify nodes exponentially infrequently in their heights.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
Pages351-362
Number of pages12
DOIs
StatePublished - 2009
Event11th International Symposium on Algorithms and Data Structures, WADS 2009 - Banff, AB, Canada
Duration: Aug 21 2009Aug 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5664 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Symposium on Algorithms and Data Structures, WADS 2009
Country/TerritoryCanada
CityBanff, AB
Period8/21/098/23/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Rank-balanced trees'. Together they form a unique fingerprint.

Cite this