Average search time. Run empirical studies to compute the average and standard deviation o...

Average search time. Run empirical studies to compute the average and standard deviation of the average length of a path to a random node (internal path length divided by tree size, plus 1) in a BST built by insertion of N random keys into an initially empty tree, for N from 100 to 10,000. Do 1,000 trials for each tree size. Plot the results in a Tufte plot, like the one at the bottom of this page, fit with a curve plotting the function 1.39 lg N - 1.85 (see exercise3.2.35 and exercise3.2.39).

Exercise 3.2.35:

Refined analysis. Refine the mathematical model to better explain the experimental results in the table given in the text. Specifically, show that the average number of compares for a successful search in a tree built from random keys approaches the limit 2 ln N + 2γ - 3 ≈ 1.39 lg N - 1.85 as N increases, where γ = .57721… is Euler’s constant. Hint: Referring to the quicksort analysis in section2.3, use the fact that the integral of 1/x approaches ln N + γ.

Exercise 3.2.39:

Average case. Run empirical studies to estimate the average and standard deviation of the number of compares used for search hits and for search misses in a BST built by running 100 trials of the experiment of inserting N random keys into an initially empty tree, for N = 104, 105, and 106. Compare your results against the formula for the average given in exercise3.2.35.

Exercise 3.2.35:

Refined analysis. Refine the mathematical model to better explain the experimental results in the table given in the text. Specifically, show that the average number of compares for a successful search in a tree built from random keys approaches the limit 2 ln N + 2γ - 3 ≈ 1.39 lg N - 1.85 as N increases, where γ = .57721… is Euler’s constant. Hint: Referring to the quicksort analysis in section2.3, use the fact that the integral of 1/x approaches ln N + γ.