let us consider binary search tree for array elements ={10,8,15,3,12}.
consider the diagram :
black circle = elements present in array
red circle = elements not present in Array ( unsuccessful search keys).
.
now suppose we search for key 1 :
we will first search at root =10 (absent). then we will drop dowm next level as (1<10) and goto left tree. value of new node = 8( not equal to 1 and 1<8) we will drop down new node where key = 3 (not equal to 1 ).
now here we know that 3 does not have any child node so we will stop here (in other words we know that array is empty)
#comparisons = 3.
similarly for other keys :
| keys(unsuccessful search) |
#comparisons |
| 1 |
3 |
| 4 |
3 |
| 9 |
2 |
| 11 |
3 |
| 13 |
3 |
| 16 |
2 |
overall comparison = 3+3+2+3+3+2 (or total external node length El)
considering unsuccessful keys = external nodes
#number of candidates = 6 (or number of internal nodes(I) +1).
so average comparisons = total comparisons/ #keys(US)
= ( El ) / (I+1) answer
