Hi,
I know the running time of Binary Search Tree i.e O(lg N). Currently i am reading a data structure book in connection with Binary Search Tree. In this topic they have mentioned the concept of IPL (Internal Path Length as the sum of all path lengths of all nodes) & used the formula : Summation (i1) li. However then they talk about average IPL as : IPL/n, but in the
Path(worst) = 1/n Summation (i1)
they did not use the term li.
I cant understand why they eliminated term li ? I have attached a picture of the book's page. Can somebody please guide me?
Zulfi.
I know the running time of Binary Search Tree i.e O(lg N). Currently i am reading a data structure book in connection with Binary Search Tree. In this topic they have mentioned the concept of IPL (Internal Path Length as the sum of all path lengths of all nodes) & used the formula : Summation (i1) li. However then they talk about average IPL as : IPL/n, but in the
Path(worst) = 1/n Summation (i1)
they did not use the term li.
I cant understand why they eliminated term li ? I have attached a picture of the book's page. Can somebody please guide me?
Zulfi.
Attachments

174.8 KB Views: 10