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.