AVL Tree

Question

Let T be a binary search tree with n nodes and Sn be the average number of comparisons required for successful search and Un be the average number of comparison required for an unsuccessful search. Then what is the relation between Sn, Un and n

Comments

https://stackoverflow.com/questions/24537366/average-complexity-of-binary-search-for-an-unsuccessful-search

Answer 1

S_n=(I(n)+n)/n

U_n=E(n)/(n+1)

S_n=(((n+1)/n)U_n-1

where S_n  be the average number of comparisons required for successful search and Un be the average number of comparison required for an unsuccessful search .

I(n) is total internal path length and E(n) is total external path length .

 

Comments

Thank you sir , but a brief explanation will make it more clear. :)

---

what is this intrernal path and external path you have taken.?

---

http://cse.iitkgp.ac.in/~pb/algo-1-pb-10.pdf

see this for more clearation.

---

What is internal and external path length?