A dichromatic framework for balanced trees

Leo J. Guibas; Robert Sedgewick

doi:10.1109/sfcs.1978.3

A dichromatic framework for balanced trees

Leo J. Guibas, Robert Sedgewick

Computer Science

Research output: Contribution to journal › Conference article › peer-review

464 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 language	English (US)
Pages (from-to)	8-21
Number of pages	14
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1978-October
DOIs	https://doi.org/10.1109/sfcs.1978.3
State	Published - 1978
Event	19th Annual Symposium on Foundations of Computer Science, SFCS 1978 - Ann Arbor, United States Duration: Oct 16 1978 → Oct 18 1978

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/sfcs.1978.3

Cite this

@article{ee55b862906e425593106cbdb6ba5c7a,

title = "A dichromatic framework for balanced trees",

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.",

author = "Guibas, {Leo J.} and Robert Sedgewick",

note = "Publisher Copyright: {\textcopyright} 1973 IEEE.; 19th Annual Symposium on Foundations of Computer Science, SFCS 1978 ; Conference date: 16-10-1978 Through 18-10-1978",

year = "1978",

doi = "10.1109/sfcs.1978.3",

language = "English (US)",

volume = "1978-October",

pages = "8--21",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - A dichromatic framework for balanced trees

AU - Guibas, Leo J.

AU - Sedgewick, Robert

PY - 1978

Y1 - 1978

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85039153497&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85039153497&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1978.3

DO - 10.1109/sfcs.1978.3

M3 - Conference article

AN - SCOPUS:85039153497

SN - 0272-5428

VL - 1978-October

SP - 8

EP - 21

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - 19th Annual Symposium on Foundations of Computer Science, SFCS 1978

Y2 - 16 October 1978 through 18 October 1978

ER -

A dichromatic framework for balanced trees

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this