Let f (N) be the average number of full nodes in a binary search tree.

a. Determine the values of f(0) and f (1).

b. Show that for N > 1

Figure 4.75 Sample input for Exercise 4.53
Euler's constant: .........4, 5
Series: .....................2-5
arithmetic: ................4-5
geometric: ...................4
harmonic: ...................5
Figure 4.76 Sample output for Exercise 4.53
c. Show (by induction) that f (N) = (N − 2)/3 is a solution to the equation in part (b), with the initial conditions in part (a).
d. Use the results of Exercise 4.6 to determine the average number of leaves in an N node binary search tree.

Transcribed Image Text:

N-1 - 2 F(N) = +EF) +f(N – i – 1)) N – 2 IX: {Series |() IX: {Series!geometric|(} {4} IX: {Euler's constant} {2} {4} IX: {Series!geometric|)} {4} IX: {Series!arithmetic|(} {4} IX: {Series!arithmetic|)} {5} IX: {Series!harmonic|(} IX: {Euler's constant} IX: {Series!harmonic|)} IX: {Series |)} {5} {5} {5} {5}