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 the average search cost in the case of a successful search in a binary search tree and in the case of an unsuccessful search, we can say that

, where is the internal path length and is the number of nodes in the tree.

**Prove that .**

and just for a reminder, , where 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

-- 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

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

where 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