Updating a balanced search tree in O(1) rotations

Research output: Contribution to journalArticle

64 Scopus citations

Abstract

Olivié has recently introduced the class of 'half-balanced' binary search trees, which have O(log n) access time but require only a constant number of single rotations for rebalancing after an insertion or a deletion. In this paper we show that a well-known class of balanced binary trees, the 'symmetric binary B-trees' of Bayer, have the same properties. This is not surprising, for Bayer's class and Oliviés class contain exactly the same binary trees.

Original languageEnglish (US)
Pages (from-to)253-257
Number of pages5
JournalInformation Processing Letters
Volume16
Issue number5
DOIs
StatePublished - Jun 10 1983

All Science Journal Classification (ASJC) codes

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

Keywords

  • Balanced search trees
  • half-balanced binary trees
  • red-black trees
  • symmetric binary B-trees

Fingerprint Dive into the research topics of 'Updating a balanced search tree in O(1) rotations'. Together they form a unique fingerprint.

  • Cite this