What are the advantages of binary search trees with all elements stored in the leaf nodes ?

Question

I'm reading Advanced Data Structures by Peter Brass, and in the begining 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 dictionnary), and an other where all objects are stored in leaves and internal nodes are only for comparisons. My problem is: I can't figure what are the advantages of the second model over the first one. Please point me out the enlightenment path.

Answer 1

well storing information objects in the nodes, we talking in this case about a trie, is usefull for fast retrival of information(faster than storing stuff in an array/hashtable, where the worst case auf acces is O(n), in the trie this is O(m) [m is the lenght of n])

look here: https://secure.wikimedia.org/wikipedia/en/wiki/Trie

In a search tree this oerations can be much more complicated(look AVL Tree O(log n) ) and so can be slower and is more compley to implement.

What data structure to choose?? Well this depends on what u want to do

Answer 2

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.