3
$\begingroup$

In the section 6.2.3 (Volume 3) Donald Knuth says:

... we can ask about the number $B_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the generating function $B_h(z) = \sum_{n\ge0} B_{nh}z^n$ for small $h$, from the relations

$$B_0(z) = 1,$$ $$B_1(z) = z,$$ $$B_{h+1}(z) = zB_h(z)(B_h(z) + 2B_{h-1}(z)).$$

I would understand this formulas if they were like this:

$$B_0 = 1$$ $$B_1 = 1$$ $$B_{h+1} = B_hB_h + B_hB_{h-1}+B_{h-1}B_h = B_h(B_h + 2B_{h-1})$$

Which means that there is only one empty tree ($h=0$), only one tree with a single node ($h = 1$) and number of other trees (of $h+1$, where $h\ge1$) can be calculated as the number of all combinations of shorter trees - having trees shorter by one on as both sub-trees ($B_hB_h$), having shorter by one on the left and shorter by two on the right ($B_hB_{h-1}$) and the wise versa ($B_{h-1}B_h$).

These formulas are actually the same as the ones from the book if $z=1$. This makes me think that it is correct.

Is my reasoning correct? And if it is, can anyone explain what this $z$ actually stands for?

$\endgroup$
5
$\begingroup$

The way I tend to interpret these parameters is to think of them as stand-ins for some type of basic structure in your enumeration problem. This might sound a bit too abstract, so let's look at a (simpler) concrete example.

Let's consider the task of enumerating linked lists. The question I'm interested in is, given a list of unit types (those whose only element is the unit $\circ$), how many lists over unit are there such that their length is $n$? Now, this question was chosen for a very simple purpose: it's easy to see what the answer is. If each element of your list can only be a single element $\circ$, then obviously there's exactly one list of size $n$.

Now, one way to solve this is to look at the inductive definition of a list. $$ \textrm{List}_{\circ} = \circ :: \textrm{List}_{\circ} ~\textrm{or}~ [] $$

This says that a list over $\circ$ is either a $\circ$ prepended to another list, or it is an empty list. Flattening out the fancy operators into tuple form, and turning the word $\rm or$ into a $+$, we have

$$ \textrm{List}_{\circ} = (\circ * \textrm{List}_{\circ}) + [] $$

Since an empty list [] can be thought of as a tuple with zero $\circ$s inside, let's rewrite it as $\circ^0 = 1$. This then gives an equation

$$ L = \circ * L + 1 $$

Suppose that we're working over the complex field, then this is equivalent to (assuming that $\circ \ne 1$) $$ L = \frac{1}{1 - \circ} = \circ^0 + \circ^1 + \circ^2 + \circ^3 + \dots $$

Now, notice that the formal power series of $L$ with respect to $\circ$ exactly specifies all of the possible lists over the unit $\circ$. That's kind of cool, but is it just a coincidence?

To find out, we turn our attention to a related problem, that of counting lists over the booleans $(\bot, \top)$. Once again, we start with the inductive definition

$$ \textrm{List}_{2} = (\bot ~\textrm{or}~ \top) :: \textrm{List}_{2} ~\textrm{or}~ [] $$

Doing the same transformation as before, we find that

$$ L_2(\bot, \top) = \frac{1}{1 - (\bot + \top)} = 1 + \bot + \top + \bot^2 + \bot\top + \top\bot + \top^2 + \bot^3 + \bot^2\top + \dots $$

Interesting, it seems like for certain enumeration problems, the inductive definition we use to specify/construct a type can be translated into this functional over the complex numbers. What's more, this functional's formal power series seems to generate a series of constructions that are isomorphic to the objects from your inductive specification. This is more or less the idea behind these generating functions: their series representation "generates" the combinatorial structures that you are studying.

Now, let's come back to the counting problem. So what if we know that $\frac{1}{1 - \top - \bot}$ represents our combinatorial class? How does this help us with the enumeration problem? Well, the counting problem asks for the number of lists that contains a certain number. This tells us that even if $\top$ and $\bot$ are distinct, they still each contribute the same number of elements (namely, 1) to the list. We can specify this "blindness" with the equality $z = \bot = \top$, so that

$$ L_2(z) = L_2(z, z) = \frac{1}{1 - 2z} = 1 + z + z + z^2 + z^2 + z^2 + z^2 + z^3 + z^3 + \dots $$

simplifying, this series yields

$$ L_2(z) = 1 + 2z + 4z^2 + 8z^3 + \dots + 2^k z^k + \dots $$

Since each of the lists under $z^3$ are lists of length 3, this series then tells us that there are $2^3$ distinct boolean lists of length 3.

Herein lies the power of these generating functions. By "erasing" properties that you don't care about (like the distinctness of true and false in a counting problem), you end up with this formal series whose coefficient gives the total count of a subclass of interest. Therefore, the question du jour of these "analytic" enumeration problems is not how one interprets giving $z$ a specific value, but rather how one can show that the function is analytic/differentiable around the origin and what its coefficients are.

This glosses over a lot of the details, but the intuition should hopefully remain. For your particular problem, we can follow the same recipe to eventually derive Knuth's tower of balanced tree construction.

Now, a height-balanced tree is a binary tree such that the height of each child of a tree is always within one unit of any other child of a tree. This gives a simple case-analysis to consider.

A balanced tree of height $h$ is a root node together with children such that they are:

  • Balanced, so that the height of both children are the same, aka $h - 1$.
  • Unbalanced but left-skewed, so that the height of the left children is larger, aka $h - 1$ and $h - 2$.
  • Unbalanced but right-skewed, so that the height of the right children is larger, aka $h - 2$ and $h - 1$.

This then yields an inductive specification

$$ BBT_h = (BBT_{h-1}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-2}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-1}, \circ, BBT_{h-2}) $$

Where the tuple $(L, \circ, R)$ denotes the balanced tree rooted at $\circ$ with the left branching to $L$ and the right branching to $R$. Transferring to the complex field, this gives $$ B_h = \circ B_{h-1}^2 + \circ B_{h_2} B_{h-1} + \circ B_{h-1} B_{h-2} $$ taking advantage of the newly found freedom of commutativity, and reassociating, we have $$ B_h(\circ) = \circ B_{h-1}(B_{h-1} + 2 B_{h-2}) $$ Since this is a two-step recurrence, we need to specify their initial conditions. $B_0$ is the class of balanced trees with zero nodes, so we have $B_0(\circ) = \circ^0 = 1$. $B_1$ is the class of balanced trees with one node, so we have $B_1(\circ) = \circ^1$. Finally, substituting $z = \circ$ gives Knuth's generating functions.

Of course, we've skipped over one bit: we haven't shown that there's some neighborhood around the origin such that $B_k(z)$'s formal series actually converges. Fortunately for us, these forms of inductive constructions are all generally admissible, so we need not worry about them here.

Finally, the last step is to characterize the coefficient of $z^k$. To be fair, the full problem is to find the coefficients of $\sum_h B_h(z)$, but it suffices to just find the coefficient for some $B_h(z)$, since we can then sum over the rest independently. There's two general strategies we can pursue:

  1. Find an explicit characterization of $B_h(z)$.
  2. Use the implicit recurrence directly and see if we can find the coefficients directly.

Here, I imagine that Knuth's approach is probably the second approach. In particular, given two functions $A(z) = a_0 + a_1 z + a_2 z^2 + \dots$ and $B(z) = b_0 + \dots$, we have $$ A(z) * B(z) = \sum_n \sum_{k \le n} a_k b_{n-k} z^n $$ and in particular $$ zA(z) = a_0z + a_1z^2 + \dots $$

Letting $[z^n]f(z) = f_n$ be the coefficient of $z^n$ in $f(z)$, then we have \begin{align*} [z^{n+1}]B_h(z) &= [z^n](B_{h-1}(z)^2 + 2B_{h_1}(z)B_{h-2}(z)) \\ &= \sum_{k \le n} ([z^k]B_{h-1}(z) + [z^k]B_{h-2}(z)) \times [z^{n-k}]B_{h-1}(z) \end{align*}

This then gives a rather mundane dynamic programming algorithm to compute these coefficients. You can also probably appeal to some analytic techniques to solve for asymptotic properties, but that's for another time.

$\endgroup$
3
$\begingroup$

The variable $z$ is known as a formal variable. It doesn't really stand for anything. However, if you want, you can consider it as standing for "vertex", as in the theory of combinatorial species.

In the special case of combinatorial species mentioned here, we are interested in counting a certain type of trees by their vertices. Denote by $\langle \mathcal{L} \rangle$ the "object" corresponding to the class $\mathcal{L}$ of trees. We will have two "rules":

  1. Addition rule: If a class $\mathcal{L}$ of trees can be partitioned into classes $\mathcal{L}_1,\ldots,\mathcal{L}_m$ then $$ \langle \mathcal{L} \rangle = \sum_{i=1}^m \langle \mathcal{L}_i \rangle. $$
  2. Multiplication rule: Let $\mathcal{L}_1,\ldots,\mathcal{L}_m$ be classes of trees. The class $\mathcal{L} = \times_{i=1}^m \mathcal{L}_i$ of tuples $(T_1,\ldots,T_m )$ of trees, where $T_i \in \mathcal{L}_i$, satisfies $$ \langle \mathcal{L} \rangle = \prod_{i=1}^m \langle \mathcal{L}_i \rangle. $$

If we denote by $z$ the tree with one vertex, then $z^n$ represents a tree with $n$ vertices, and $Cz^n$ represents $C$ trees with $n$ vertices. This amounts to giving an interpretation of $\langle \mathcal{L} \rangle$ which respects the rules above: $\langle \mathcal{L} \rangle = \sum_i c_n z^n$, where $c_n$ is the number of trees having $n$ vertices in $\mathcal{L}$.

We can now interpret Knuth's recurrence. Let $\mathcal{B}_n$ denote the class of balanced trees on $n$ vertices. Then:

  1. There is a single balanced tree of height $0$, so $\langle \mathcal{B}_0 \rangle = z^0 = 1$.
  2. There is a single balanced tree of height $1$, so $\langle \mathcal{B}_1 \rangle = z^1 = z$.
  3. A balanced tree of height $h+1$ consists either of (1) a root and a pair of balanced trees of height $h$ ($\langle \mathcal{B}_1 \rangle \langle \mathcal{B}_h \rangle^2$, given the product rule), or (2) a root and a pair of balanced trees of heights $h,h-1$ ($\langle \mathcal{B}_1 \rangle \langle \mathcal{B}_h \rangle \langle \mathcal{B}_{h-1} \rangle$), or (3) a root and a pair of balanced trees of heights $h-1,h$ (same as previous case). Invoking the addition rule, we get $$ \langle \mathcal{B}_h \rangle = z \langle \mathcal{B}_h \rangle^2 + 2z \langle \mathcal{B}_h \rangle \langle \mathcal{B}_{h-1} \rangle. $$

These formulas are useful, since you can compute Knuth's $B_h$ using polynomial multiplication (which is equivalent to dynamic programming), and then extract the number of balanced binary trees of height $h$ as the coefficient of $z^h$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.