What are the advantages of storing all elements in the leaf nodes?

Question

I'm reading Advanced Data Structures by Peter Brass.

In the beginning of the chapter on search trees, he stated that there is two models of search trees - one where nodes contain the actual object (the value if the tree is used as a dictionary), and an other where all objects are stored in leaves and internal nodes are only for comparisons.

What are the advantages of the second model over the first one?

Answer 1

One of the big advantages of a binary tree where data is only in the leaf nodes is that you can partition based on elements that are not in your dataset.

For example, if I have a possible dataset of 0-1 million, but the vast majority of items are either at the high end or low end but not in the middle, I may still want my first compare against 500,000 - even though that number is not in my data set. If every node had data, I could not do this. While not normally needed in theory, I've run into many times that partitioning based on a value outside my data simplified implementation.