# Internal and external path length of a binary search tree

• Jul 15th 2013, 04:40 PM
Flexdec
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 $S_N$ the average search cost in the case of a successful search in a binary search tree and $U_S$ in the case of an unsuccessful search, we can say that
$S_N = I/N$, where $I$ is the internal path length and $N$ is the number of nodes in the tree.

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

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

REMINDER:
Attachment 28836
• Jul 16th 2013, 10:05 AM
johng
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 SN 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

$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

$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):

$S_N=2(1+{1\over N})H_N-3$ where $H_N$ is the Nth partial harmonic sum.
• Jul 17th 2013, 11:28 AM
Flexdec
Re: Internal and external path length of a binary search tree
Thanks!! I guess my teacher just forgot about the +1 haha