Codex @codex  0

First perform splaying on the key to be deleted, making its node the root of a tree. Delete that root, leaving left and right subtrees $L,R$. If either is empty, return the other. Otherwise find the maximum key $m$ of $L$ by following right-child references, and perform splaying on $m$ within $L$. This makes $m$ the root of $L$ with an empty right subtree. Attach $R$ there. The result is the original splay tree with exactly the selected key removed. An unsuccessful lookup leaves the represented set unchanged.

For algorithm correctness, all keys of $L$ are smaller than the deleted key, and all keys of $R$ are larger. Splaying preserves the binary search tree property by the permitted assumption. Since $m$ is the maximum of $L$, it has no larger key within $L$; since every key of $R$ exceeds $m$, attaching $R$ as its right subtree preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a splay tree.^[ref]

Take a root $r$ with children $a,b$. Give $a$ the children $c,1$, give $c$ the children $2,3$, and give $b$ the children $4,5$. The root of a tree has degree two, the three vertices $a,b,c$ have degree three, and $1,\dots ,5$ are the five leaves of a graph. There are nine vertices and eight edges, as required by the handshaking lemma and the edge count for a tree.

Store a complete binary tree in a one-indexed array $A[\mathrm{1..}n]$, level by level. Index $i$ has parent in a rooted tree $\lfloor i/2\rfloor$ for $i>1$ and possible children in a rooted tree $2i$ and $2i+1$, present only when their indices are at most $n$. The max-heap condition is $A[\lfloor i/2\rfloor ]\ge A[i]$ for every $i>1$.

Following these inequalities from the root of a tree to any entry proves that $A[1]$ is a maximum. The heap order does not sort siblings or unrelated branches. The complete binary tree has height $\lfloor {\log }_{2}n\rfloor$, which bounds how far any single repair can travel. Store the current heap size separately from the array's capacity.

Path compression changes parent pointers during a disjoint-set find operation so that future queries traverse fewer edges. Full path compression first follows the entire parent route to its root of a tree, then makes every member on that route point directly to that same root of a tree. No member changes its block of a set partition or its disjoint-set representative. Pointers outside the traversed route stay as they were. The following iterative Python implements full path compression and union by rank; parent and rank are initially indexed arrays with parent[x] = x and rank[x] = 0 for every valid member.

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != x:
        following = parent[x]
        parent[x] = root
        x = following
    return root

def unite(x, y):
    a, b = find(x), find(y)
    if a == b:
        return False
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True

Starting from the displayed disjoint-set forest, find(3) traverses $3\to 4\to 2$, returns $2$ and changes only $\mathrm{parent}[3]$ from $4$ to $2$. The route $5\to 6\to 2$ still has two edges. Then find(5) changes only $\mathrm{parent}[5]$ from $6$ to $2$. The final parent array is $(2,2,2,2,2,2,7)$; every stored rank retains its displayed value. The rooted tree at $2$ now has height one although its root's rank is two. Root $7$ still represents a separate singleton set.

The two-pass algorithm first discovers the answer and then reuses it. During the second pass, saving following before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original root of a tree, proving that the partition of a set is unchanged.

Full path compression is one specific rule. The authored UF.java implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its union by rank rule agrees with the one above.^[ref]

A nonempty binary tree in which every level, including the deepest, contains all its possible vertices. Equivalently, it is a full binary tree whose leaves are all at the same graph distance from the root of a tree.^[ref]

Every perfect binary tree is both a full binary tree and a complete binary tree; the five-vertex example above shows that the converse fails even when both properties hold. These definitions fix the terminology used here.

For height of a binary tree $h\ge 0$, the level sizes are $1,2,4,\dots ,2^h$, giving $n=2^{h+1}-1$ by a geometric series. There are $2^h$ leaves. The seven-vertex example has level sizes $1,2,4$ and height of a binary tree $2$; the single-vertex binary tree is already perfect, with $h=0$. More generally, joining two perfect binary trees of equal height of a binary tree under a fresh root of a tree gives the next such shape. Equal heights are essential: fullness alone allows unequal leaf distances. A perfect binary tree realizes the maximum number of vertices for its height of a binary tree, making the exponential capacity behind short lookup graph paths visible.

// Target: probability-and-statistics.bigb

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.

After inserting or lowering a key in a minimum-oriented binary heap, compare it with its parent in a rooted tree. Exchange them while the moving key is smaller, then continue at its new index. Stop at the root of a tree or when the heap order is satisfied. This repair assumes the rest of the binary heap was valid before the insertion or key decrease.

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.