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

20/07/2021

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.