Give every node the rational stop cost shown below. A node may either stop and pay its own cost, or refine and pay the already optimized costs of its children. The shaded nodes form the selected complete pruning.
Reading the drawing
Each node gives its address, stop cost and optimal subtree cost. Shaded nodes show the selected mixed-depth cut; tree edges show the alternatives compared.
Drawing labels and data 16 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
\(\varnothing\)
\(20\,|\,9\)
\(0\)
\(5\,|\,3\)
\(1\)
\(8\,|\,6\)
\(00\)
\(1\,|\,1\)
\(01\)
\(2\,|\,2\)
\(10\)
\(7\,|\,2\)
\(11\)
\(4\,|\,4\)
\(000\)
\(1\,|\,1\)
\(001\)
\(2\,|\,2\)
\(010\)
\(2\,|\,2\)
\(011\)
\(3\,|\,3\)
\(100\)
\(1\,|\,1\)
\(101\)
\(1\,|\,1\)
\(110\)
\(2\,|\,2\)
\(111\)
\(3\,|\,3\)
node labels: stop cost \(c_v\) \(|\) optimal subtree cost \(V(v)\)
Read the calculation from the bottom upward
At \(10\), the children cost \(1+1=2\), better than stopping for \(7\). At \(11\), stopping costs \(4\), better than \(2+3=5\). The right subtree therefore costs \(6\), better than its stop cost \(8\). The left subtree costs \(1+2=3\), better than \(5\). At the root, \(3+6=9\) beats \(20\). The unique optimum is
All \(26\) complete prunings are separately enumerated and give the same minimum. At equality, the rule stops, making the selector deterministic. A singleton tree needs no comparison. The costs here are supplied numbers. The theorem optimizes that stated additive objective; it does not prove those numbers encode the best denoising criterion. Coupled costs that cannot be written as a sum of selected-node costs need a different optimizer.
Read this as
Global optimality follows from the exact stop-or-refine decomposition of a complete pruning, not from a greedy assumption.