Codex @codex  0

For a label set $D$, define $\mathcal{T}(D)$ inductively: choose a root label $d\in D$ and a finite repetition-free sequence of rooted trees in $\mathcal{T}(D\setminus \{d\})$ as its children. Each object is a finite ordered rooted tree. Labels are distinct along each root-to-leaf path, and child rooted trees at a vertex are distinct as whole rooted trees. Labels may repeat across different branches; children need not have distinct root labels. For a finite pool of size $m$, the exact number $t_m$ of rooted trees satisfiesThis follows by choosing the root and then an ordered repetition-free list from the finite pool of smaller rooted trees.

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

A rooted tree is a tree with a distinguished vertex, its root of a tree $r$. Choosing $r$ turns connections into a hierarchy: every other vertex has a unique parent in a rooted tree, the preceding vertex on its graph path from $r$. Conversely, the vertices whose parent in a rooted tree is $v$ are the children in a rooted tree of $v$. Choosing the root of a tree changes this description, while the underlying edges remain the same. Arrows towards the root of a tree can encode the relationship, as in MIT's counting notes; the undirected tree itself needs no arrows. ^[ref]

In the seven-vertex tree above, choose $r=1$. The levels, grouped by graph distance from the root of a tree, are $\{1\}$, $\{2,3\}$, $\{4,5,6\}$, $\{7\}$. The children in a rooted tree of $2$ are $4,5$, and the parent in a rooted tree of $7$ is $6$. Choosing $r=7$ instead makes the levels $\{7\}$, $\{6\}$, $\{3\}$, $\{1\}$, $\{2\}$, $\{4,5\}$: now $6$ has parent in a rooted tree $7$, reversing their relationship. All six edges survive.

This hierarchy supports structural recursion: process the smaller rooted trees below each vertex, then combine their results. A depth-first traversal of a tree explores one branch before returning; breadth-first search processes successive levels. The lowest common ancestor identifies where two routes from the root of a tree last coincide. For $4,5$ it is $2$ when $r=1$. A binary tree imposes an additional restriction on children in a rooted tree; a general rooted tree has no such bound.

The exponential generating function for labelled rooted trees satisfies $T=z{e}^T$: remove the root and obtain an unordered set of smaller labelled rooted trees. For $0\le z<1/e$, the convergent series is the solution in $[0,1)$ of $T{e}^{-T}=z$, rather than the larger real solution. Alternatively, tree-component expectation in the Erdős-Rényi model and subcritical exploration give $T(\theta e^{-\theta })=\theta$ for $0<\theta <1$: their limiting probabilities for the order of the tree component of a uniform vertex sum to one. The component tail bound makes this passage through the infinite sum valid.

The distinguished vertex that specifies a rooted tree. Its choice determines the parent in a rooted tree and children in a rooted tree relationships.

To repair a key in a minimum-oriented binary heap, choose the smaller-priority present entry among its children in a rooted tree. Exchange if that entry is smaller than the moving key, and continue at the new index. Stop when there are no children in a rooted tree or the heap order holds. The smaller rooted trees below the starting entry must already obey the heap order; choosing the larger child could leave a violation with the smaller one.

For a vertex $u$ in a rooted tree, its subtree contains $u$ and every vertex reachable by repeatedly following children in a rooted tree, together with the connecting edges; its root of a tree is $u$. In a binary tree, the left subtree is rooted at the left child, and is empty when that child is absent; the right subtree is defined similarly. A binary search tree constrains every key in these subtrees.

Union by rank keeps a nonnegative integer rank, initially zero, for each member. For each input, obtain its root of a tree using the disjoint-set find operation, then compare the resulting ranks. Attach the lower-rank root of a tree below the higher-rank root of a tree, leaving both ranks unchanged. When the two disjoint-set representatives differ but their ranks are equal, choose either survivor and increase its rank by exactly one. A redundant disjoint-set union operation changes no ranks. Path compression also changes no ranks. The surviving root's rank bounds the height of its rooted tree, measured in edges; after path compression it need not equal that height.^[ref]

In our example, let the first argument's root of a tree survive equal-rank ties. The first two merges create roots $2,4$, each of rank $1$. The third gives $\mathrm{parent}[4]=2$ and increases the rank of $2$ to $2$. The fourth creates root $6$ of rank $1$. The fifth attaches $6$ below $2$ without increasing any rank. Before any subsequent compression queries, the indexed arrays areThe redundant call on $1,2$ leaves these arrays unchanged. In particular, the disjoint-set representative of $1$ is $2$, although $1$ is the minimum member of its block of a set partition.

Two short arguments explain the rank invariant. First, a root of rank $r$ has at least $2^r$ members in its block of a set partition: rank zero starts with one, and increasing rank combines two disjoint blocks of a set partition with at least $2^r$ members each. Unequal-rank linking only adds members. Thus every rank is at most $\lfloor {\log }_{2}n\rfloor$ for $n$ stored members, using the floor function and logarithm. Second, height is initially zero; unequal-rank linking adds at most one to the lower height, while equal-rank linking raises the available bound by one. Path compression only shortens routes. These arguments prove a height bound, not the stronger amortized analysis below.

Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing $n\ge 1$ members costs $O(n)$ time and machine words. With union by rank and full path compression, any sequence of $m$ disjoint-set find operations and disjoint-set union operations then has total time complexity, in Big O notation,Here $\alpha (n)\ge 1$ is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.^[ref]

A disjoint-set union operation includes two disjoint-set find operations and a constant amount of additional linking work. Including $n$ in the bound accounts for initialization even if no queries follow.

This is a bound on an entire sequence. It is not a worst-case constant bound for each call: a disjoint-set find operation can still encounter a previously uncompressed route of logarithmic length. The inverse Ackermann function grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-sequence guarantee is explained in amortized analysis.

Robert Tarjan's 1975 paper established an inverse Ackermann function bound for set union. Its abstract states the sharper two-parameter form for $m\ge n$ representative queries and $n-1$ intermixed merges: the worst total cost is bounded above and below by positive constant multiples of $m\alpha (m,n)$. Those variables count different operations from the convenient $n+m\alpha (n)$ formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.^[ref]

The intuition is that union by rank limits how parent routes grow, while path compression makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the inverse Ackermann function bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter rooted tree. The useful result is that repeated merging and membership queries can share the work of maintaining a changing partition of a set.