Section 6.2.1: Searching an Ordered Table

Exercise 21. [20] [20] Draw the binary tree corresponding to interpolation search when N = 10.

Verified: no
Solve time: 4m10s

---

Solution

Let the keys be

$$ K_1<K_2<\cdots<K_{10}, $$

and let the unsuccessful-search intervals (gaps) be

$$ (K_0,K_1),\ (K_1,K_2),\ \ldots,\ (K_{10},K_{11}), $$

where

$$ K_0=-\infty,\qquad K_{11}=+\infty. $$

For interpolation search, Algorithm I determines the next comparison from the endpoints of the current interval. To obtain a comparison tree depending only on $N$, one uses Knuth's standard model in which the $N+1$ gaps are equally spaced. Thus, if a subproblem contains $g$ gaps, the keys are regarded as lying at equally spaced positions, and the interpolation formula becomes

$$ m=l+\left\lfloor \frac{(x-K_l)(r-l)} {K_r-K_l} \right\rfloor . $$

Since the keys are equally spaced, the quantity

$$ \frac{x-K_l}{K_r-K_l} $$

is exactly the fraction of the distance from $K_l$ to $K_r$. Hence the probe index is determined by the position of the gap containing $x$. The binary tree is obtained by evaluating this rule for each subinterval.

Root

Initially $l=1$, $r=10$. There are $11$ gaps.

For equally spaced keys,

$$ m

1+\left\lfloor 9\frac{x-K_1}{K_{10}-K_1} \right\rfloor . $$

The transition from $m=4$ to $m=5$ occurs halfway between $K_5$ and $K_6$. Therefore gaps $0,1,2,3,4$ lead to indices $1,2,3,4$, while gaps $5,6,7,8,9,10$ lead to indices $5,6,7,8,9,10$. Hence the first comparison is with $K_5$.

Thus the left subtree corresponds to gaps $0,\ldots,4$, and the right subtree to gaps $5,\ldots,10$.

Left subtree

The interval contains the keys $K_1,\ldots,K_4$ together with $5$ gaps.

Applying the interpolation formula to this interval gives

$$ m

1+\left\lfloor 3\frac{x-K_1}{K_4-K_1} \right\rfloor . $$

The break between $m=1$ and $m=2$ is midway between $K_2$ and $K_3$. Therefore the five gaps are divided into

$$ {0,1},\qquad {2,3,4}, $$

and the next comparison is with $K_2$.

For the interval containing gaps $0,1$, there are two gaps and one key, namely $K_1$, so the next comparison is with $K_1$.

For the interval containing gaps $2,3,4$, there are three gaps and two keys, namely $K_3$ and $K_4$. The interpolation formula gives the first probe $K_4$. Hence the left subtree is

$$ \begin{array}{c} 2\ /\qquad\backslash\ 1\qquad4 \end{array} $$

Right subtree

The interval contains the keys $K_6,\ldots,K_{10}$ together with $6$ gaps.

With equally spaced keys,

$$ m

6+\left\lfloor 4\frac{x-K_6}{K_{10}-K_6} \right\rfloor . $$

The change from $m=7$ to $m=8$ occurs midway between $K_8$ and $K_9$. Hence the six gaps are divided into

$$ {5,6,7},\qquad {8,9,10}, $$

and the next comparison is with $K_8$.

For the interval corresponding to gaps $5,6,7$, the remaining keys are $K_6,K_7$. Applying the interpolation formula to these two equally spaced keys gives the first probe $K_7$.

For the interval corresponding to gaps $8,9,10$, the remaining keys are $K_9,K_{10}$. Applying the same calculation gives the first probe $K_{10}$.

Therefore the right subtree is

$$ \begin{array}{c} 8\ /\qquad\backslash\ 7\qquad10 \end{array} $$

Combining the two parts, the binary tree corresponding to interpolation search for $N=10$ is

$$ \boxed{ \begin{array}{cccccccccccc} &&&&5&&&&\[1ex] &&/&&&&\backslash&&\[1ex] &2&&&&&&8&\[1ex] /&\backslash&&&&&&/&\backslash\[1ex] 1&&4&&&&7&&10 \end{array}} $$

The $11$ external nodes represent the $11$ gaps

$$ 0,1,\ldots,10, $$

corresponding to unsuccessful searches. Thus the internal nodes of the comparison tree are

$$ 5,\ 2,\ 1,\ 4,\ 8,\ 7,\ 10. $$

Hence this is the interpolation-search tree when $N=10$.