Harder, Better, Faster, Stronger

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.

If we use a naïve comparison scheme, each keys ask for two (potentially expensive) comparisons. One to test if the sought value, is smaller than a key ; one to test if they’re equal. If neither tests is true, we move on to the next key. If none of the tests are true, it is an “else” case and we go down the rightmost branch. That scheme does way more work than necessary and would ask for comparison per node (because there are keys per node).

The main problem with this straightforward approach is that comparisons can be very expensive. While comparing two integral types (int and the like) is often thought of as “free”, comparing string is expensive. So you clearly do not want to test two strings twice, once for < and once for =. The much better approach is to use a three-way comparison, also known as the “spaceship operator”.

Leave a Comment