Fringe analysis of binary search trees

Date
1985
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

Fringe analysis is a technique to analyze search trees. It was first formulated by A. Yao to estimate the expected number of nodes in 2-3 trees and B-trees. This technique has been used and studied by many researchers. We present a formal definition of a fringe and an algorithm to find a fringe base for fringe analysis in binary search trees. We also define classes of fringe (balanced) trees depending on a parameter d. These fringe balanced trees can be used to estimate the performance of certain balanced trees. The technique is applied to AVL trees, Internal Path Reduction trees and 1-2 brother trees.

Description
Keywords
Data structures (Computer science), Binary system (Mathematics), File organization (Computer science)
Citation