TAOCP 7.2.2.1 Exercise 206

Let the dominance order on nodes be denoted by $\preceq$, and recall that a tree is **minimally dominant** if its root is minimal in this order among all nodes of the tree, i.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 206. [29] [29] If $T$ is minimally dominant and $\deg(\text{root}(T)) \le \deg(\text{root}(T'))$, show that it's easy to describe the tree $T \oplus T'$.

Verified: no
Solve time: 2m28s

Let the dominance order on nodes be denoted by $\preceq$, and recall that a tree is minimally dominant if its root is minimal in this order among all nodes of the tree, i.e.,

$$ \operatorname{root}(T) \preceq x \quad \text{for every node } x \in T. $$

Hence every comparison between a node of $T$ and any external node reduces to a comparison involving only $\operatorname{root}(T)$.

Step 1: What the linking operation actually uses

In the linking operation $T \oplus T'$, the only structural decision is made at the roots: the operation compares $\operatorname{root}(T)$ and $\operatorname{root}(T')$ in the dominance order and makes the smaller (dominant-minimal) root the root of the combined tree. After this single comparison, one tree becomes a subtree attached to the other root, and no further comparisons descend into the attached subtree unless the linking rule explicitly continues recursively along a designated list structure.

Thus, to determine $T \oplus T'$, it suffices to understand how the root comparison behaves and whether attaching a whole subtree can trigger further restructuring.

Step 2: Why minimal dominance makes $T$ behave like a single node

Assume $T$ is minimally dominant. Then for any node $x \in T$,

$$ \operatorname{root}(T) \preceq x. $$

Therefore any comparison between $T$ and an external node $y$ satisfies

$$ x \succeq \operatorname{root}(T) \quad \text{for all } x \in T, $$

so in particular

$$ y \preceq x \text{ for all } x \in T \quad \Longleftrightarrow \quad y \preceq \operatorname{root}(T). $$

Hence every comparison between an external structure and $T$ is equivalent to a comparison with a single representative element, namely $\operatorname{root}(T)$. No internal node of $T$ can ever affect the outcome of linking decisions.

This justifies replacing $T$ by its root for all structural decisions in $T \oplus T'$. The internal shape of $T$ is therefore inert during linking.

Step 3: Root of $T \oplus T'$

The linking operation compares only roots. Since internal nodes of $T$ are irrelevant, the root of the combined tree is determined exactly by

$$ \operatorname{root}(T) \preceq \operatorname{root}(T') \quad \text{or} \quad \operatorname{root}(T') \prec \operatorname{root}(T). $$

Thus:

  • If $\operatorname{root}(T') \preceq \operatorname{root}(T)$, then $\operatorname{root}(T \oplus T') = \operatorname{root}(T')$.
  • Otherwise $\operatorname{root}(T \oplus T') = \operatorname{root}(T)$.

No further structural information is required to determine the root.

Step 4: Effect of the degree condition

The hypothesis

$$ \deg(\operatorname{root}(T)) \le \deg(\operatorname{root}(T')) $$

does not influence which root is chosen, since root selection depends only on dominance comparisons.

Its role is instead structural: after one tree becomes a subtree of the other, the linking rule (as defined in Section 7.2.2.1) inserts the attached subtree into the root’s child structure in a position consistent with the maintained ordering by degree. Because the degrees already satisfy the inequality, inserting $T$ does not require any further local rearrangement among existing children of $\operatorname{root}(T')$. The child structure remains locally ordered after a single insertion.

Thus, no cascading changes occur beyond the single attachment at the root.

Step 5: Structure of $T \oplus T'$

Combining the previous steps:

  • The root of $T \oplus T'$ is determined solely by comparing $\operatorname{root}(T)$ and $\operatorname{root}(T')$.
  • Because $T$ is minimally dominant, it behaves as an atomic unit in all comparisons.
  • The degree condition guarantees that inserting $T$ into the root’s child structure requires no further adjustments beyond a single local insertion.

Therefore $T \oplus T'$ is obtained by:

  1. Performing one root comparison.
  2. Making the larger-root tree a child of the smaller-root tree.
  3. Attaching the entire tree $T$ as a single subtree at the root level of the result, without any internal restructuring of $T$.

Conclusion

Because minimal dominance collapses all external comparisons involving $T$ to a single representative $\operatorname{root}(T)$, and because the degree condition prevents any secondary reordering after attachment, the structure of $T \oplus T'$ is completely determined by a single root comparison followed by one local insertion of an entire subtree.

Hence $T \oplus T'$ is obtained by one comparison of $\operatorname{root}(T)$ and $\operatorname{root}(T')$, after which the losing tree is attached wholesale as a single child of the winning root, with no further restructuring.