Chapter 12, Problem 3P

(a)

Program Plan Intro

To argue the average depth of a node in tree T is $\frac{1}{2}{\displaystyle \sum _{x\in T}d(x,T)=\frac{1}{2}P(T)}$ .

(b)

Program Plan Intro

To argue that if a tree has n nodes then $P(T)=P(TL)+P(TR)+n-1$ where $TL$ is left sub-tree and $TR$ is right sub-tree of the tree T .

(c)

Program Plan Intro

To show the average total path length of BST is $P(n)=\frac{1}{n}{\displaystyle \sum _{i=0}^{n-1}(P(i)}+P(n-i-1)+n-1)$ .

(d)

Program Plan Intro

To rewrite the equation $P(n)$ as $P(n)=\frac{2}{n}{\displaystyle \sum _{k=1}^{n-1}P(k)+\Theta (n)}$ .

(e)

Program Plan Intro

To explain the randomized version of quicksort takes the cost of $P(n)=O(n\lg n)$ .

(f)

Program Plan Intro

To describe the comparison of quicksort is equals to the comparisons need to insert the elements in BST.