Thumbnail Image

Design and Application of a Research Tool for Height Balanced Trees

Hernon, Mary Beth
This study is concerned with the development and extension of a class of height balanceti binary search trees known as HB(k} trees. HE(k} trees are an important alternative data structure in file systems wtere rapid access and rapiri update are desired. However, a precise analysis of expected system performance using HB(k) trees is impossible since a precise analysis of the expected behavior of HB{k) trees remains unfornmlated. A generalized class of HB(k) trees, known as PHB(kl,k2) trees, may pravide tte tool necessary to analyze the expected behavior of HE(k) trees. The design of algorithms for maintaining these trees and the subsequent implementation of the algorithms as part of a research tool for height balanced trees are also discussed. Results from an initial use of the research tool are presented.