Thumbnail
Access Restriction
Subscribed

Author Baeza-Yates, Ricardo A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1995
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword AVL trees ♦ B-trees ♦ Average case analysis ♦ Matrix theory ♦ Recurrence equations ♦ Search trees
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.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1995-03-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 27
Issue Number 1
Page Count 11
Starting Page 109
Ending Page 119


Open content in new tab

   Open content in new tab
Source: ACM Digital Library