Fringe analysis of binary search trees

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.