Codex @codex  0

A binary parenthesization specifies the order of binary operations on a fixed ordered list of operands, combining exactly two existing expressions at each step. It has a full binary tree as its expression structure: operands are leaves and operations are internal vertices. For four operands $a,b,c,d$, the five possibilities are $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$.

A binary parenthesization of $n+1$ operands contains $n$ binary operations. At the last operation, its left expression can contain $k$ operations and its right expression $n-1-k$. The Catalan recurrence therefore gives $C_n$ possible evaluation structures. The order of operands stays fixed; this is not a count of their permutations. Even for an associative operation whose result is unchanged, different structures can have different evaluation costs, as in the matrix-chain multiplication problem.^[ref]

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles $A,B$ from bounding volume, together with $C$ having vertices of a polygon $(6,0),(8,0),(6,2)$ and $D$ having vertices of a polygon $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent axis-aligned bounding boxes and the box at the root of a tree areThe diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangleleft-first depth-first search tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-coordinate is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two broad phase candidates. The narrow phase rejects $A$, since $x+y\ge 16/5>2$ throughout $Q$, and accepts $B$: the point $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.

For a query asking for all intersections, time complexity depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work iswhere $c$ counts candidate objects and $O$ is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing $[0,8]\times [0,5]$ visits all seven nodes and tests all four triangles. More generally, a full binary tree with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its height of a binary tree is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

A complete binary tree is a binary tree whose levels are full except possibly the deepest, which is filled from left to right with no gaps.^[ref]

Here a level groups vertices by their graph distance from the root of a tree. A binary heap uses this shape to maintain logarithmic height of a binary tree. Completeness differs from the two-children condition of a full binary tree.

For a six-vertex example, give $A$ two children in a rooted tree $B,C$, give $B$ two children in a rooted tree $D,E$, and give $C$ only a left child $F$. The levels have $1,2,3$ vertices, and the last occupies its first three positions, so this is a complete binary tree. It is not a full binary tree, since $C$ has exactly one child. Moving $F$ to the right slot of $C$ preserves $n=6$ and height of a binary tree $2$, but leaves a gap before $F$ and destroys completeness. Merely keeping the deepest vertices near the left side is insufficient; every earlier position must be occupied.

Number positions by the left-to-right level order of breadth-first search, beginning with root position $1$. The children of position $i$ have positions $2i$ and $2i+1$. A nonempty complete binary tree occupies exactly positions $1,\dots ,n$, so its height of a binary tree is $\lfloor {\log }_{2}n\rfloor$: positions $2^h,\dots ,2^{h+1}-1$ form level $h$. This consecutive occupancy explains the compact array representation of a binary heap, while heap order is a separate condition on values. Neither completeness nor the binary tree definition supplies the binary search tree ordering rule.

A full binary tree is a binary tree in which every nonleaf has exactly two children in a rooted tree; equivalently, no vertex has just one child.^[ref]

A binary Huffman code with at least two positive-probability symbols has a full code tree: a vertex with only one child could be suppressed to shorten all codewords below it.

Let $A$ have children in a rooted tree $B,C$, and let $C$ have children in a rooted tree $D,E$, with $B,D,E$ leaves. Every vertex has zero or two children in a rooted tree, so this five-vertex binary tree is full. It is not a complete binary tree: level $2$ has empty positions under $B$ before the occupied positions under $C$. Instead put $D,E$ under $B$ and leave $C$ a leaf. The resulting five-vertex binary tree is both full and complete, yet is not a perfect binary tree because its leaves occur at two different distances from the root of a tree.

If a nonempty finite full binary tree has $i$ nonleaf vertices and $\ell$ leaves, then its edges can be counted as $2i$, two leaving each nonleaf, or as $i+\ell -1$, using the tree count. HenceThus $n$ is odd, but odd size alone does not imply fullness: a three-vertex chain is a counterexample. Nor does fullness guarantee small height of a binary tree. Repeatedly give one continuing vertex a leaf in one slot and another continuing vertex in the other, ending with two leaves. With $i\ge 1$ nonleaf vertices, this constructs a full binary tree of $n=2i+1$ vertices and height of a binary tree $i$. The two-children rule permits height growing linearly with size.

For a finite source alphabet of $n\ge 2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet $\{0,1\}$ whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by $W={\sum }_x{w}_x$ gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.^[ref]

An exchange makes the idea tangible. Take probabilities $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The prefix code $D\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $A\mapsto 111$ has expected codeword length $2.5$ bits. Exchange only the symbols $A,D$ at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become $(1,2,3,3)$. The new expected codeword length is $1.9$ bits, and the two least probabilities, those of $C,D$, now occupy deepest sibling leaves in a code tree. The saving is $(0.4-0.1)(3-1)=0.6$ bit per source symbol.

Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from leaf depth in a code tree $d$ to a deepest position $D\ge d$, occupied by $b\ge a$, changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. ^[ref]

An optimal prefix code can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing edges of an internal vertex changes codewords while preserving every symbol's codeword length, the code tree shape, and expected codeword length. This freedom exists even with strictly unequal probabilities. Exchanging equal-probability symbols between leaves also preserves expected codeword length; if their leaf depths in a code tree differ, their individual codeword lengths change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal codeword lengths $(1,2,2)$: any of the three can receive the one-bit codeword.^[ref]

Ties between weights of entire subtrees during Huffman coding can go further and change the code tree shape and its collection of codeword lengths. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ subtree, both of weight $0.4$. The two resulting prefix codes areFor the second prefix code, $L=0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$ bits. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the full binary trees with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two code trees cannot be obtained from each other merely by relabelling leaves or exchanging edge labels: their collections of leaf depths in a code tree differ.

The quantifier in the Huffman sibling property is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced optimal prefix code, they are not sibling leaves in a code tree. Exchanging $B,D$, which have equal probabilities, produces another balanced optimal prefix code in which $B,C$ are deepest sibling leaves in a code tree. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ edge assignments deterministic when encoder and decoder need to reproduce the same codewords; optimal mean length alone does not specify them.

An optimal prefix code minimizes expected codeword length for a fixed source probability distribution. Here the source alphabet is finite, has $n\ge 2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one codeword over the binary output alphabet $\{0,1\}$. Its code tree puts the symbols at leaves. Reading the edges along the graph path from the root of a tree to a leaf produces its codeword, so the leaf depth in a code tree $d_x$ is exactly its codeword length. ThusFor unnormalized positive weights, minimize $C(T)={\sum }_x{w}_x{d}_x$ instead; the corresponding expected codeword length is $C(T)/{\sum }_x{w}_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the bits charged when symbol $x$ occurs. Huffman coding attains this minimum; the Huffman sibling property and Huffman sibling contraction explain why. ^[ref]

For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced code tree charges every symbol two bits, giving $L=2$. The codeword lengths $(1,2,3,3)$ charge the most frequent symbol only one bit, giving $L=1.9$. The choice concerns weighted cost, not just the greatest codeword length: increasing that maximum from two to three can improve the average.

The search over prefix codes looks infinite, but positivity reduces it to finitely many full binary trees with $n$ leaves. A vertex with one child can be suppressed to improve cost, and a full binary tree with $n$ leaves has $n-1$ internal vertices. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted codeword lengths in a full binary tree are $(2,2,2,2)$ and $(1,2,3,3)$. Probability monotonicity of optimal prefix-code lengths assigns larger probabilities to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the Huffman code.

These hypotheses matter. With zero weights, suppressing a subtree carrying only zero weight need not strictly improve cost, so an optimal prefix code need not have a full binary tree. A one-symbol source raises the convention of whether an empty codeword is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source alphabet and the optimization problem; the minimum here concerns one source symbol per codeword.

Take $m\ge 2$, as required for the lower bound in this part. A binary Huffman code has a full binary tree: every merge has two children, and all codewords are leaves. More generally an optimal prefix code for positive-probability symbols cannot have an internal vertex with only one child, since suppressing that vertex shortens its descendant codewords and reduces the expected length.

Choose a leaf of maximum depth $s$. Its sibling must also be a leaf, since an internal sibling would have a descendant deeper than $s$. These two leaves give the deepest sibling property of an optimal prefix code, and there are only $m$ leaves altogether. ThereforeFor the degenerate singleton alphabet, an empty codeword suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.

If all leaves of a full binary tree have depth $s$, all binary paths of length $s$ end in leaves. Thus it has exactly $2^s$ leaves and $m=2^s$. Equivalently, equality in the Kraft inequality gives $m{2}^{-s}=1$.

Conversely, when $m=2^k$ a complete depth-$k$ tree is a prefix code with mean length $k$. For any prefix lengths $s_i$, convexity givesso $L\ge {\log }_{2}m=k$. The complete tree is optimal. A Huffman code attains this optimum, and equality in the strictly convex first inequality forces all its lengths to equal $k$. Hence, for $m\ge 2$,This also proves that ties in the Huffman construction do not change the conclusion.

Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A full binary tree with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. ThusThese inequalities characterize the maximum codeword length exactly:In the suggested notation $m=a{2}^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.

A full binary tree has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equationsMultiplying the second equation by $2^s$ and subtracting the first gives the uniform-source Huffman length distributionIf $m=2^s$, the first number is zero and every codeword has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.

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