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

Kurt Mehlhorn

Abstract

We describe a fringe analysis of AVL-trees (and 2-3-trees and HB-trees) under random insertions and deletions. Previously, only the case of random insertions was dealt with. Keywords AVL-trees random insertions and deletions fringe analysis
BibTeX
@article{mehlhorn1982partial,
  author = {Kurt Mehlhorn},
  title = {{A Partial Analysis of Height-Balanced Trees Under Random Insertions and Deletions}},
  journal = {SIAM Journal on Computing},
  year = {1982},
  doi = {10.1137/0211061},
}

Loading related content...

Figure