Binary Trees are optimal… except when they’re not.


The best case depth for a search tree is O(\log_b n), if b is the arity (or branching) of the tree. Intuitively, we know that if we increase b, the depth goes down, but is that all there is to it? And if not, how do we chose the optimal branching b?


While it’s true that an optimal search tree will have depth O(\log_b n), we can’t just increase b indefinitely, because we also increase the number of comparisons we must do in each node. A b-ary tree will have (in the worst case) b-1 keys, and for each, we must do comparisons for lower-than and equal (the right-most child will be searched without comparison, it will be the “else” of all the comparisons). We must first understand how these comparisons affect average search time.

Read the rest of this entry »