A Partial Analysis of Random Height-Balanced Trees

Abstract

The collection of nodes nearest to the external nodes in a random height-balanced tree is analyzed. We determine the proportion of balanced nodes in this section of the tree, and find the average number of single and double rotations which occur at the minimum height during insertions. If $\bar B_n $ denotes the average number of balanced nodes in a random height-balanced tree with n internal nodes, we show that $\frac{{10}}{{21}} (n + 1) \leqq \bar B_n \leqq \frac{6}{7}(n + 1) - 1$ for $n \geqq 6$.