TAOCP 7.2.2.1 Exercise 203
Equation (95) defines $T \otimes T'$ as the binary operation that combines two search trees by grafting $T'$ onto the terminal structure of $T$, with identity element $\square$ (the single-node tree).
Section 7.2.2.1: Dancing Links
Exercise 203. [M15] Equation (95) shows that the binary operation $T \otimes T'$ on search trees has an identity element, '■'. Is that operation (a) associative? (b) commutative?
Verified: yes
Solve time: 1m26s
Solution
Equation (95) defines $T \otimes T'$ as the binary operation that combines two search trees by grafting $T'$ onto the terminal structure of $T$, with identity element $\square$ (the single-node tree). Concretely, $T \otimes T'$ is obtained by replacing each terminal node of $T$ by a copy of $T'$ while preserving the branching structure of $T$.
(a) Associativity
Let $T_1, T_2, T_3$ be search trees. Consider $(T_1 \otimes T_2) \otimes T_3$.
Form $T_1 \otimes T_2$ by replacing every terminal node of $T_1$ by a copy of $T_2$. In the resulting tree, each terminal node originates from a terminal node of $T_2$ attached at a terminal node of $T_1$. Applying $\otimes T_3$ replaces every terminal node of this intermediate structure by a copy of $T_3$, so every terminal node of $T_2$ becomes the root of a copy of $T_3$, while the outer structure of $T_1$ remains unchanged.
Now consider $T_1 \otimes (T_2 \otimes T_3)$. First form $T_2 \otimes T_3$ by replacing each terminal node of $T_2$ by a copy of $T_3$. Then replace each terminal node of $T_1$ by this expanded structure.
In both constructions, each terminal node of $T_1$ is replaced by a copy of $T_2$, and each terminal node of that copy is replaced by a copy of $T_3$. The resulting tree consists of a copy of $T_1$ whose leaves are expanded uniformly into copies of $T_2$, and then into copies of $T_3$, with identical adjacency relations.
Since both procedures produce identical node-for-node expansions of $T_1$ with two successive substitutions applied in the same order, the resulting trees coincide. Hence
$(T_1 \otimes T_2) \otimes T_3 = T_1 \otimes (T_2 \otimes T_3).$
This completes the proof. ∎
(b) Commutativity
Let $T_1$ and $T_2$ be search trees such that both contain at least one nontrivial branching structure. In $T_1 \otimes T_2$, the outer branching structure is determined by $T_1$, since the first level of choices corresponds to $T_1$ before any expansion occurs. In $T_2 \otimes T_1$, the outer branching structure is determined by $T_2$.
These two constructions produce search trees with different root-to-leaf decision orders unless $T_1$ and $T_2$ are structurally identical to the identity tree $\square$ or degenerate to a single path. In general, the first decision level in $T_1 \otimes T_2$ corresponds to choices in $T_1$, while in $T_2 \otimes T_1$ it corresponds to choices in $T_2$, so the branching structure at the root differs.
Therefore
$T_1 \otimes T_2 \ne T_2 \otimes T_1$
in general, and the operation is not commutative.
This completes the proof. ∎