Fringe analysis revisited
- 1 March 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 27 (1) , 109-119
- https://doi.org/10.1145/214037.214103
Abstract
Fringe analysis is a technique used to study the average behavior of search trees. In this paper we survey the main results regarding this technique, and we improve a previous asymptotic theorem. At the same time, we present new developments and applications of the theory that allow improvements in several bounds on the behavior of search trees. Our examples cover binary search trees, AVL-trees, 2–3 trees, and B-trees.Keywords
This publication has 32 references indexed in Scilit:
- The analysis of heuristics for search treesActa Informatica, 1993
- Unbalanced multiway trees improved by partial expansionsActa Informatica, 1992
- Performance of B/sup +/-trees with partial expansionsIEEE Transactions on Knowledge and Data Engineering, 1989
- Some average measures in m-ary search treesInformation Processing Letters, 1987
- The analysis of a fringe heuristic for binary search treesJournal of Algorithms, 1985
- Dense multiway treesACM Transactions on Database Systems, 1981
- Space utilization and access path length in B-treesInformation Systems, 1980
- Higher order analysis of random 1–2 brother treesBIT Numerical Mathematics, 1980
- Comparing insertion schemes used to update 3-2 treesInformation Systems, 1979
- Some observations on random 2–3 treesInformation Processing Letters, 1979