TAOCP 5.4.1 Exercise 5
A selection tree used for replacement selection represents $P$ external nodes as the leaves of a complete binary tree, with internal nodes storing comparison results along the path to the root.
Section 5.4.1: Multiway Merging and Replacement Selection
Exercise 5. [00] [00] True or false: Replacement selection using a tree works only when P is a power of 2 or the sum of two powers of 2.
Verified: yes
Solve time: 1m28s
A selection tree used for replacement selection represents $P$ external nodes as the leaves of a complete binary tree, with internal nodes storing comparison results along the path to the root. Such a structure does not require that $P$ match any special arithmetic form; when the last level of the tree is not full, the remaining positions are either unused or filled with sentinel values such as $+\infty$ so that they never affect the tournament outcome. The update and replacement operations depend only on the fixed parent–child relationships in the tree and not on any divisibility condition on $P$.
The construction and maintenance of the tree therefore work for every positive integer $P$, independent of whether $P$ is a power of $2$ or a sum of two powers of $2$. Hence the stated restriction is not necessary.
This completes the proof. ∎