TAOCP 2.3.2 Exercise 8

Let us reformulate the ordering of Exercise `2.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 8. [M20] Exercise 2.3.1-25 shows how an ordering between the information stored in the individual nodes of a binary tree may be extended to a linear ordering of all binary trees. The same construction leads to an ordering of all trees, under the natural correspondence. Reformulate the definition of that exercise, in terms of trees.

Verified: yes
Solve time: 1m20s

Solution

Let us reformulate the ordering of Exercise 2.3.1-25 in terms of ordinary trees, using the natural correspondence between forests and binary trees. In 2.3.1-25, a linear ordering of binary trees is defined recursively as follows. Given two binary trees B and B', let \operatorname{INFO}(B) denote the information stored in the root of B, and let L(B) and R(B) denote the left and right subtrees of B. Then B \prec B' if and only if one of the following conditions holds:

  1. \operatorname{INFO}(B) \prec \operatorname{INFO}(B') in the ordering of node information; or
  2. \operatorname{INFO}(B) = \operatorname{INFO}(B') and L(B) \prec L(B'); or
  3. \operatorname{INFO}(B) = \operatorname{INFO}(B'), L(B) = L(B'), and R(B) \prec R(B').

Here \prec on subtrees is defined recursively, and empty trees are considered minimal.

Now let T and T' be ordinary trees (not binary) with roots \operatorname{root}(T) and \operatorname{root}(T'), and let T_1, T_2, ..., T_m and T'_1, T'_2, ..., T'_n be the ordered lists of subtrees of \operatorname{root}(T) and \operatorname{root}(T'), respectively. The natural correspondence maps T to a binary tree B(T) whose root is \operatorname{root}(T), whose left subtree is the binary tree corresponding to the forest (T_1, ..., T_m), and whose right subtree is empty (or corresponds to the remaining forest if T is part of a larger forest).

Using this correspondence, we define a recursive linear ordering of trees as follows. We write T \prec T' if and only if one of the following holds:

  1. \operatorname{root}(T) \prec \operatorname{root}(T') in the ordering of node information; or
  2. \operatorname{root}(T) = \operatorname{root}(T') and the sequence of subtrees (T_1, T_2, ..., T_m) is lexicographically less than (T'_1, T'_2, ..., T'_n) under the same tree ordering. Explicitly, this means that for the least index i such that T_i \ne T'_i, we have T_i \prec T'_i; if no such i exists and m < n, then T \prec T'.

Formally, let F(T) = (T_1, ..., T_m) be the forest of subtrees of \operatorname{root}(T). Define the lexicographic ordering of forests recursively: a forest F = (T_1, ..., T_m) precedes a forest F' = (T'_1, ..., T'_n) if either m = 0 and n > 0, or there exists a minimal index i such that T_i \ne T'_i and T_i \prec T'_i, or T_i = T'_i for all i \le \min(m,n) and m < n. Then T \prec T' if either \operatorname{root}(T) \prec \operatorname{root}(T') or \operatorname{root}(T) = \operatorname{root}(T') and F(T) \prec F(T') lexicographically.

This ordering is well-defined, total, and compatible with the natural correspondence. It reduces exactly to the binary-tree ordering of 2.3.1-25 when trees are mapped to their binary equivalents. Empty trees are minimal, and the recursion terminates because every tree has finitely many nodes. This defines a linear ordering on the class of all trees.

This completes the proof.

∎