FRINGE ANALYSIS REVISITED

Authors
BAEZAYATES RA
Citation
Ra. Baezayates, FRINGE ANALYSIS REVISITED, ACM computing surveys, 27(1), 1995, pp. 109-119
Citations number
61
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
ACM computing surveys → ACNP
ISSN journal
03600300
Volume
27
Issue
1
Year of publication
1995
Pages
109 - 119
Database
ISI
SICI code
0360-0300(1995)27:1<109:FAR>2.0.ZU;2-H
Abstract
Fringe analysis is a technique used to study the average behavior of s earch trees. In this paper we survey the main results regarding this t echnique, and we improve a previous asymptotic theorem. At the same ti me, we present new developments and applications of the theory that al low improvements in several bounds on the behavior of search trees. Ou r examples cover binary search trees, AVL-trees, 2-3 trees, and B-tree s.