TAOCP 6.2.1 Exercise 15

Let $T_k$ denote the Fibonacci tree of order $k$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.1: Searching an Ordered Table

Exercise 15. [M19] [M19] For what values of k does the Fibonacci tree of order & define an optimal search procedure, in the sense that the fewest comparisons are made on the average?

A424 SEARCHING 6.2.1

Verified: yes
Solve time: 1m36s

Solution

Let $T_k$ denote the Fibonacci tree of order $k$. Let $N_k$ be its number of internal (circular) nodes. From the construction in Section 6.2.1,

$$ N_k = F_{k+1}-1. $$

Let $I(T)$ denote the internal path length of a binary search tree $T$, that is, the sum of the depths of all internal nodes, where the root has depth $0$ and each edge increases depth by $1$.

For a fixed $n$, an optimal search procedure in the sense of minimum average number of comparisons corresponds to a binary search tree with $n$ nodes having minimal internal path length among all binary search trees with $n$ nodes and equal probabilities for successful searches. A standard level-counting argument shows that among all binary trees with $n$ nodes, the minimum of $I(T)$ is attained by a complete binary tree, since at depth $d$ at most $2^d$ nodes can appear, and placing any node at depth $d+1$ instead of a vacant position at depth $d$ strictly increases the total sum of depths.

Let $C_n$ denote a complete binary tree with $n$ nodes. Then $C_n$ is optimal for size $n$.

The problem reduces to determining all $k$ such that $T_k$ is complete in this extremal sense for $N_k$ nodes.

The structure of $T_k$ is given recursively: the root has left subtree $T_{k-1}$ and right subtree $T_{k-2}$ (up to the index shifts described in the text). Hence the height $h(k)$ satisfies

$$ h(k) = 1 + h(k-1), $$

since the left branch decreases the order by $1$ at each step. With $h(0)=h(1)=0$, this gives

$$ h(k) = k-1 \quad (k \ge 1). $$

For a complete binary tree with $N_k$ nodes, the height is the smallest integer $h$ such that

$$ N_k \le 2^{h+1}-1. $$

Since $N_k = F_{k+1}-1$, direct comparison determines when the Fibonacci tree can match this optimal height behavior.

Small values of $k$

For $k=0$, $N_0 = F_1-1 = 0$. The tree is empty, and $I(T_0)=0$, which is minimal.

For $k=1$, $N_1 = F_2-1 = 0$. The same conclusion holds.

For $k=2$, $N_2 = F_3-1 = 1$. Both possible binary search trees consist of a single node, hence internal path length is $0$, which is minimal.

For $k=3$, $N_3 = F_4-1 = 2$. The Fibonacci tree has a root and one child. Every binary search tree on two nodes has one node at depth $0$ and one at depth $1$, hence internal path length equals $1$ in all cases, and no tree yields a smaller value.

For $k=4$, $N_4 = F_5-1 = 4$. The Fibonacci tree has one subtree of size $2$ and one subtree of size $1$ attached to the root. The subtree of size $2$ is necessarily a chain of length $2$, since it corresponds to $T_3$. The resulting depth multiset is ${0,1,2,1}$, hence

$$ I(T_4)=0+1+2+1=4. $$

For any binary search tree with $4$ nodes, minimal internal path length is achieved by distributing nodes as evenly as possible across levels. Any such optimal shape has one node at depth $0$, two nodes at depth $1$, and one node at depth $2$, since level capacities are $1,2,4,\dots$ and the first level cannot be filled without using level $2$. This yields internal path length $4$, so $T_4$ is optimal.

Failure for $k \ge 5$

For $k \ge 5$, the height of $T_k$ is $k-1 \ge 4$. Hence $T_k$ contains at least one node at depth $k-1 \ge 4$.

For $k=5$, $N_5 = F_6-1 = 7$. A complete binary tree on $7$ nodes has height $2$, since $2^{3}-1=7$. Every node in such a tree lies at depth at most $2$, and every leaf lies at depth exactly $2$. Thus its internal path length equals

$$ 0 + 2\cdot 1 + 4\cdot 2 = 10. $$

In $T_5$, the existence of a node at depth $4$ forces internal path length at least $4$ larger than any arrangement avoiding depth $4$, since replacing a node at depth $4$ by a node at depth $2$ (which is available in the complete tree distribution) reduces the total by at least $2$ per level difference. Hence $I(T_5) > 10$, so $T_5$ is not optimal.

For $k \ge 6$, the same argument strengthens, since $T_k$ has height $k-1 \ge 5$, while the complete tree on $N_k = F_{k+1}-1$ nodes has height strictly less than $k-1$ because

$$ F_{k+1}-1 < 2^{k-1}-1 \quad \text{for } k \ge 5, $$

so the complete tree places all nodes at depth at most $k-2$. The presence of at least one node at depth $k-1$ in $T_k$ forces a strictly larger internal path length than the optimal complete arrangement.

Conclusion

The Fibonacci tree $T_k$ defines an optimal search procedure precisely for those $k$ for which its shape coincides with a complete binary tree in the sense of minimal internal path length. This occurs exactly for

$$ k = 0,1,2,3,4. $$

For $k \ge 5$, the height imbalance forces strictly larger internal path length than the optimal binary search tree on the same number of nodes.

This completes the proof. ∎