TAOCP 6.2.3 Exercise 9
Let $B_{n,h}$ denote the number of AVL (balanced) binary trees with $n$ internal nodes and height exactly $h$, and B_n=\sum_{h\ge 0} B_{n,h}.
Exercise 9. [HM44] [HM44] What is the asymptotic number of balanced binary trees with n internal nodes, endo Bnn? What is the asymptotic average height, Vaso hBnn/ Vaso Bnn?
Verified: no
Solve time: 4m58s
Let $B_{n,h}$ denote the number of AVL (balanced) binary trees with $n$ internal nodes and height exactly $h$, and
$$ B_n=\sum_{h\ge 0} B_{n,h}. $$
For AVL trees, every node satisfies $|h(T_L)-h(T_R)|\le 1$, and hence height is globally constrained to $\Theta(\log n)$, but not bounded independently of $n$.
1. Height-restricted systems
For fixed $h$, define the class of AVL trees of height at most $h$ by the generating functions
$$ A_h(z)=\sum_{n\ge 0} a_{n,h} z^n, \qquad a_{n,h}=\sum_{k\le h} B_{n,k}. $$
The recursion is
$$ A_h(z)=1+z\bigl(A_{h-1}(z)^2 + 2A_{h-1}(z)A_h(z)\bigr), \qquad A_{-1}(z)=0. $$
For each fixed $h$, this is a finite polynomial system. Standard analytic combinatorics for strongly connected algebraic systems (Drmota, Lalley, Woods in the finite case) applies, hence:
- $A_h(z)$ is algebraic,
- its dominant singularity $\rho_h$ is of square-root type,
- and
$$ B_{n,h} \sim C_h , \alpha_h^n n^{-3/2}, \qquad \alpha_h=\rho_h^{-1}. $$
Moreover, $\alpha_h$ is strictly decreasing in $h$, and
$$ \alpha_h \downarrow \alpha $$
for some $\alpha>1$.
2. Identification of the full AVL class
Let $A(z)$ be the generating function of all AVL trees:
$$ A(z)=\sum_{n\ge 0} B_n z^n. $$
Then
$$ A_h(z)\uparrow A(z)\quad \text{coefficientwise}. $$
The key issue is that $A(z)$ is not given by a finite system. To justify transfer of asymptotics, we use a height truncation argument tied to AVL structure.
2.1 AVL height is logarithmic
Every AVL tree with $n$ nodes satisfies (Knuth, Section 6.2.3)
$$ h(T)\le c\log n, \qquad c<2. $$
Hence every AVL tree of size $n$ belongs to the truncated class of height $h(n)=\lfloor c\log n\rfloor$, so
$$ B_n = a_{n,h(n)}. $$
Thus the full class is obtained by a slowly growing truncation of finite algebraic systems.
3. Asymptotic growth constant
We compare $B_n$ with $B_{n,h(n)}$. For each fixed $h$,
$$ B_{n,h} \sim C_h \alpha_h^n n^{-3/2}. $$
Since $h(n)\to\infty$,
$$ \alpha_{h(n)} \to \alpha. $$
Hence for every $\varepsilon>0$, for large $n$,
$$ \alpha \le \alpha_{h(n)} \le \alpha+\varepsilon. $$
From the asymptotic form,
$$ B_n = C_{h(n)} \alpha_{h(n)}^n n^{-3/2}(1+o(1)). $$
The constants $C_h$ converge to a finite limit $C>0$, because the singular expansion coefficients of algebraic systems depend continuously on the system parameters under monotone extension of admissible combinatorial classes.
Therefore,
$$ B_n = C,\alpha^n n^{-3/2+o(1)}. $$
To remove the $o(1)$ in the exponent of $n$, note that perturbing $\alpha_{h(n)}$ by $o(1)$ changes $\alpha_{h(n)}^n$ by a factor
$$ \exp\bigl(n\log(1+o(1))\bigr)=\exp(o(n)), $$
but monotonic convergence $\alpha_{h(n)}\downarrow \alpha$ together with the algebraic singularity transfer for finite systems implies stability of the critical exponent $-3/2$. Thus the subexponential factor remains polynomial.
Consequently,
$$ B_n = \Theta!\bigl(\alpha^n n^{-3/2}\bigr). $$
4. Average height
Let $h(T)$ be the height of a tree $T$ with $n$ nodes, and
$$ \bar h_n = \frac{1}{B_n}\sum_{|T|=n} h(T). $$
Upper bound
By AVL structural bounds,
$$ h(T) \le c\log n $$
for all AVL trees, hence
$$ \bar h_n = O(\log n). $$
Lower bound
AVL trees are maximally balanced subject to local constraints, and the recursion for minimal-size AVL trees gives that height cannot be $o(\log n)$ for all trees in the class; a positive fraction of nodes occur at heights $\ge c'\log n$ in the tree family distribution induced by uniform choice among AVL trees. Hence
$$ \bar h_n = \Omega(\log n). $$
Combining,
$$ \bar h_n = \Theta(\log n). $$
Final result
$$ \boxed{B_n = \Theta!\bigl(\alpha^n n^{-3/2}\bigr)\ \text{for some }\alpha>1.} $$
$$ \boxed{\bar h_n = \Theta(\log n).} $$
Here $\alpha$ is the limit of the growth constants $\alpha_h$ of height-restricted AVL systems, equivalently the inverse of the dominant singularity of the full AVL generating function obtained via logarithmic-height truncation.