Updating a balanced search tree in O(1) rotations

Robert Endre Tarjan

doi:10.1016/0020-0190(83)90099-6

Updating a balanced search tree in O(1) rotations

Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

65 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 language	English (US)
Pages (from-to)	253-257
Number of pages	5
Journal	Information Processing Letters
Volume	16
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(83)90099-6
State	Published - Jun 10 1983
Externally published	Yes

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

Access to Document

10.1016/0020-0190(83)90099-6

Cite this

@article{48750f24fb084c028864526e937ec04d,

title = "Updating a balanced search tree in O(1) rotations",

abstract = "Olivi{\'e} 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{\'e}s class contain exactly the same binary trees.",

keywords = "Balanced search trees, half-balanced binary trees, red-black trees, symmetric binary B-trees",

author = "Tarjan, {Robert Endre}",

year = "1983",

month = jun,

day = "10",

doi = "10.1016/0020-0190(83)90099-6",

language = "English (US)",

volume = "16",

pages = "253--257",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Updating a balanced search tree in O(1) rotations

AU - Tarjan, Robert Endre

PY - 1983/6/10

Y1 - 1983/6/10

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

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

KW - Balanced search trees

KW - half-balanced binary trees

KW - red-black trees

KW - symmetric binary B-trees

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

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

U2 - 10.1016/0020-0190(83)90099-6

DO - 10.1016/0020-0190(83)90099-6

M3 - Article

AN - SCOPUS:0020763964

SN - 0020-0190

VL - 16

SP - 253

EP - 257

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Updating a balanced search tree in O(1) rotations

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this