A Partial Analysis of Height-Balanced Trees under Random Insertions and Deletions

DOI10.1137/0211061zbMath0496.68029OpenAlexW1970018186MaRDI QIDQ3960118

Kurt Mehlhorn

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211061

zbMATH Keywords

data structuresrandom insertionsaverage behaviorbalanced treesfringe analysisrandom deletionsAVL-trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (7)

Balance in AVL trees and space cost of brother trees ⋮ Expected behaviour analysis of AVL trees ⋮ A trivial algorithm whose analysis is not: a continuation ⋮ Improved bounds for the expected behaviour of AVL trees ⋮ Unnamed Item ⋮ Higher order analysis of random 1–2 brother trees ⋮ Maintaining Ideally Distributed Random Search Trees without Extra Space

This page was built for publication: A Partial Analysis of Height-Balanced Trees under Random Insertions and Deletions