The best case depth for a search tree is , if
is the arity (or branching) of the tree. Intuitively, we know that if we increase
, the depth goes down, but is that all there is to it? And if not, how do we chose the optimal branching
?
While it’s true that an optimal search tree will have depth , we can’t just increase
indefinitely, because we also increase the number of comparisons we must do in each node. A
-ary tree will have (in the worst case)
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.