Comparing insertion schemes used to update 3-2 trees

摘要

A set of difference equations which represents transformations that occur to classes of subtrees of 3-2 trees under random insertions is developed. A solution of these equations represents the average relative frequency of subtree occurrence. These results are used in estimating average storage and insertion costs. A technique is presented for estimating an implementation parameter (the probability of a key shifting to a neighboring node under insertion) which allows comparison of various insertion strategies.