Portal de Periódicos da CAPES

Stratified balanced search trees

1983; Springer Science+Business Media; Volume: 18; Issue: 4 Linguagem: Inglês

10.1007/bf00289574

1432-0525

Jan Van Leeuwen, Mark H. Overmars,

Stochastic processes and statistical mechanics

We develop a new perspective on trees, that enables us to distinguish and analyse many different subclasses of known classes of (height-)balanced search trees in a uniform manner. The approach shows that a great many different local constraints, including an arbitrary degree of density, can be enforced on everyday balanced search tree models, without losing the O(log n) bound on the time for insertions, deletions and finds. The theory extends known concepts from the study of B-trees.