You could use the surname field as the key field for each node of the tree, and have the data field be a pointer to either a substructure that contained all the records that satisfied that key (linked list, another tree, whatever suits your application best).
Alternatively, the key field could just be letters of the alphabet cascading to subtrees of letters of the alphabet so that s-m-i-t-h would be the traversal path to reach the Smiths, while s-u-l-l-i-v-a-n would lead you to the Sullivans. The overhead for this technique is horrendous, but it's hellaciously fast to search.
However, unless this is for something like a homework assignment where you're REQUIRED to use a tree, or you're working with a HUGE database that would completely fill up your RAM, I'd recommend using a hash table of last names instead of a tree. The searches will (usually, generally, almost always) be MUCH faster (best case O(1) is pretty close to the average case if the table size is more than 2n).
|
