My Math Forum Average search cost of an unsuccessful search in a BST?

 Applied Math Applied Math Forum

July 16th, 2013, 05:25 AM   #1
Newbie

Joined: Jul 2013

Posts: 1
Thanks: 0

Average search cost of an unsuccessful search in a BST?

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.

Thanks a lot for your help!

REMINDER:
Attached Images
 mathforum.jpg (22.9 KB, 160 views)

 Tags average, bst, cost, search, unsuccessful

### cost of unsuccessful search

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post sigma123 Math Books 1 October 4th, 2012 05:39 AM sigma123 Linear Algebra 0 August 7th, 2012 01:53 AM Mr. Clueless Algebra 4 May 22nd, 2012 06:09 PM Mr. Clueless Calculus 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top