Why is the number of comparisons in a BST missing key lookup about 2 ln N? In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average. I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have 2 ln N compares?
The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.