Balancing exchange for a uniform optimal prefix code
= Balancing exchange for a uniform optimal prefix code
For an equiprobable source, an optimal binary prefix tree has leaf depths differing by at most one. If one leaf has depth $t$ and a deepest sibling pair has depth $s\ge t+2$, split the shallow leaf into two children and collapse the deep pair into its parent. The number of leaves is unchanged and their total depth decreases by $s-t-1>0$, contradicting optimality.
// Target: probability-and-statistics.bigb