3.3.44 Average search time. Run empirical studies to compute the average and stan- dard deviation of the average length of a path to a random node (internal path length divided by tree size) in a red-black BST built by insertion of N random keys into an initially empty tree, for N from 1 to 10,000. Do at least 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 lg N-.5 3.3.45 Count rotations. Instrument your program for exercISE 3.3.43 to plot the number of rotations and node splits that are used to build the trees. Discuss the results. 3.3.46 Height. Instrument your program for EXERCISE 3.3.43 to plot the height of red-black BSTs. Discuss the results. 20 g N-.5 0 operations 100 10000 Average path length to a random node in a red-black BST built from random keys 3.3.44 Average search time. Run empirical studies to compute the average and stan- dard deviation of the average length of a path to a random node (internal path length divided by tree size) in a red-black BST built by insertion of N random keys into an initially empty tree, for N from 1 to 10,000. Do at least 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 lg N-.5 3.3.45 Count rotations. Instrument your program for exercISE 3.3.43 to plot the number of rotations and node splits that are used to build the trees. Discuss the results. 3.3.46 Height. Instrument your program for EXERCISE 3.3.43 to plot the height of red-black BSTs. Discuss the results. 20 g N-.5 0 operations 100 10000 Average path length to a random node in a red-black BST built from random keys