What is the advantage of leaf trees vs. node trees?

Question

In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine):

"...two different models of search trees, either of which can be combined with much of the following material, but one of which is strongly preferable.

If we compare in each node the query key with the key contained in the node and follow the left branch if the query key is smaller and the right branch if the query key is larger, then what happens if they are equal? The two models of search trees are as follows:

1. Take left branch if query key is smaller than node key; otherwise take the right branch, until you reach a leaf of the tree. The keys in the interior node of the tree are only for comparison; all the objects are in the leaves.

2. Take left branch if query key is smaller than node key; take the right branch if the query key is larger than the node key; and take the object contained in the node if they are equal."

The author calls these Model 1 and Model 2 respectively. A figure from the book gives an example of each:

The author talks some more about the difference between these types of trees, including

1. The maximum number of keys each type can store as a function of height h ($2^h$ vs. $2^{h+1}-1$ respectively in model 1 and 2 respectively)
2. The number of comparisons on the key while traversing an interior node (1 vs 2 respectively)
3. Each key appearing up to two times in a tree (once in an interior node and once as a leaf node) in model 1 vs the key appearing exactly once in model 2.

He then says:

Model 2 became the preferred textbook version because in most textbooks the distinction between object and its key is not made: the key is the object. Then it becomes unnatural to duplicate the key in the tree structure. But in all real applications, the distinction between key and object is quite important. One almost never wishes to keep track of just a set of numbers; the numbers are normally associated with some further information, which is often much larger than the key itself.

In some literature, where this distinction is made, trees of model 1 are called leaf trees and trees of model 2 are called node trees (Nievergelt and Wong 1973). Our preferred model of search tree is model 1, and we will use it for all structures but the splay tree (which necessarily follows model 2).

(Please make note of the emphasised bits.)

My understanding of what the author is talking about is that in practice the key itself is not the ultimate object of search, and in fact one wants to associate a (possibly large or variable sized) record with each key, so the question is how one can efficiently associate this record with the key. His solution is the Model 1 tree. Looking at his implementation of the structure that defines a Model 1 node (technically this is C code - the posting of which I suspect doesn't bode well for questions posted on this site - but hopefully my question is language-agnostic and applies to the "pointer-machine model" in general):

typedef struct tr_n_t {key_t      key;
                   struct tr_n_t   *left;
                   struct tr_n_t  *right;
               /* possibly additional information */
                         } tree_node_t;

Now the way a leaf node is identified is when the right pointer is NULL (more language-agnostically, a pointer that does not point to any valid memory object), and the left pointer then points to the stored record. (Again at the risk of talking about implementation-specific stuff, one would be expected to do some kind of type casting at this point to retrieve the actual object.)

My question is: can we not get the same effect from a Model 2 tree simply by including a pointer to the associated record as an additional piece of information (i.e. in addition to the key, and left and right pointers) in each node?

What am I missing?

[The author does mention an implementation-related advantage of Model 1 that I can accept: that the structure of a model 1 tree is more regular than a model 2 tree, because in the former an interior node always has both left and right subtrees, whereas in the latter an interior node might be missing a left or right subtree. But I do not get the other advantage he claims.]

Answer 1

You don't quote the reasoning of P. Braß, if he gives any, so we can only guess.

I would like to distinguish two cases.

1. Data are stored as values, i.e. in place.
2. Data are stored by reference.

In the first case, the size of the "inner" tree would blow up arbitrarily. For every step in the search, we would have to load a potentially big node into the cache. That would increase the real cost of the search considerably (and arbitrarily, depending on the data type)! In such a scenario, using type 1 is indeed preferable as the search data structure itself contains only the information needed for performing the search.

In the second case -- which is the default in reference-based languages like e.g. Java -- this effect is present but minor: instead of two pointers, every node stores three. In such a scenario, I would prefer type 2 because it requires less storage in total.

---

Implementation-related side note: If you assign data (references) to inner nodes, they probably have some generic type Node<T: Comparable> (in modern languages). That means that the compiler may not be able optimize the search code as much as it could if the exact type were statically known. The specifics depend on the language, type system and compiler, though.