A comparative study of height-balanced tree

Height-balanced trees (H-trees), a recently proposed data structure, is a variant of B-trees. An H([beta], [gamma], [delta]) tree is defined by three parameters: [beta], the size of a node; [gamma], the minimal number of grandsons which a node must have; and [delta], the minimal number of leaves which bottom nodes must have. The purpose of this research is to study H-trees empirically. Algorithms, to insert and delete elements, are implemented. The results of our experiments confirm the validity of existing theories. For example, by varying the parameters [delta] and [gamma], significant changes in the tree's performance are observed: the height of H-trees decreases as [gamma] increases, and the storage utilization increases as [delta] increases. Moreover, comparisons of H-trees with other variants of B-trees are shown to demonstrate the superiority of H-trees. Specifically, the average storage utilization of H-trees may be higher than that of B-trees by almost 20%.