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 Bₙ denotes the average number of balanced nodes in a random height-balanced tree with n internal nodes, we show that 1021 (n + 1) Bₙ 6/7(n + 1) - 1 for n 6.
No takes yet. Share an insight, caveat, or question.
Mark R. Brown (1979) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: