A dichromatic framework for balanced trees

Leo J. Guibas, Robert Sedgewick

Research output: Contribution to journalConference articlepeer-review

456 Scopus citations


In this paper we present a uniform framework for the implementation and study of balanced tree algorithms. We show how to imhcd in this framework the best known balanced tree techniques and then use the framework to develop new which perform the update and rebalancing in one pass, Oil the way down towards a leaf. We conclude with a study of performance issues and concurrent updating.

Original languageEnglish (US)
Pages (from-to)8-21
Number of pages14
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1978
Event19th Annual Symposium on Foundations of Computer Science, SFCS 1978 - Ann Arbor, United States
Duration: Oct 16 1978Oct 18 1978

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'A dichromatic framework for balanced trees'. Together they form a unique fingerprint.

Cite this