1 Attachment(s)

Internal and external path length of a binary search tree

I'm really bugging on a question I hope somebody here can help me!

If we note by $\displaystyle S_N$ the average search cost in the case of a successful search in a binary search tree and $\displaystyle U_S$ in the case of an unsuccessful search, we can say that

$\displaystyle S_N = I/N$, where $\displaystyle I$ is the internal path length and $\displaystyle N$ is the number of nodes in the tree.

**Prove that $\displaystyle U_N=\frac{N}{N+1}(S_N+2)$.**

and just for a reminder, $\displaystyle E =I+2N$, where $\displaystyle E$ is the external path length of a binary search tree.

REMINDER:

Attachment 28836

Re: Internal and external path length of a binary search tree

Hi,

What do you mean by average cost? The usual idea is to count the number of key comparisons in a search. I'm taking my answer directly from D. E. Knuth, Vol.3, Searching and Sorting, p. 410. I have 100% confidence in this source. So if you let S_{N} be the average number of comparisons in a successful search of a binary search tree with N nodes (assuming each of the N keys is equally likely as a search argument), then

$\displaystyle S_N=1+{I\over N}$ -- this is 1 more than your formula??

Next assume that an unsuccessful search is for a key that is equally likely to be in any of the N+1 intervals determined by the N keys of the tree. Then

$\displaystyle U_N={E\over N+1}={I+2N\over N+1}={N\over N+1}(S_N-1+2)={N\over N+1}(S_N+1)$

If you read a few more pages in Knuth, you get the nice formula (assuming the tree was built initially by inserting the N keys in random order):

$\displaystyle S_N=2(1+{1\over N})H_N-3$ where $\displaystyle H_N$ is the Nth partial harmonic sum.

Re: Internal and external path length of a binary search tree

Thanks!! I guess my teacher just forgot about the +1 haha