Updating a balanced search tree in O(1) rotations

Research output: Contribution to journalArticlepeer-review

65 Scopus citations


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
Issue number5
StatePublished - Jun 10 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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


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

Cite this