For this assignment, we will be completing three separate exercises from the textbook to explore sorting algorithms: problems 3.3.44 and 3.3.45 and 3.3.446on page 456. Here are the specifications.

1. Average search time: Run empirical studies to compute the average and standard deviation of the average length if a path to a random node (internal path length divided by tree size, plus 1) 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 page 457, fit with a curve plotting the function lg n 0.5.
2. Count rotations. Instrument your BST program to plot the number of rotations and node splits that are used to build the trees. Discuss the results.
3. Height. Instrument your BST program to plot the height of red-black BSTs. Discuss the results.

please use java for the code thank you!!

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