A dichromatic framework for balanced trees

Leo J. Guibas, Robert Sedgewick

Research output: Contribution to journalConference article

381 Scopus citations

Abstract

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
Volume1978-October
StatePublished - Jan 1 1978
Externally publishedYes
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

  • Computer Science(all)

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

  • Cite this