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.