Are there practical applications (or other reasons) to teach (2,3) and AVL search trees with both keys and the associated information (as opposed to only search keys) in the internal nodes, as opposed to internal nodes having only keys and leaves having the information associated to them?
Two generic Data Structures implementing the Dynamic Dictionary Abstract Data Type are "(2,3) Trees" and "AVL Trees". Such a dynamic dictionary data structure implements (at least) the methods insert(key,info), search(key), remove(key,info). When teaching those, in order to simplify, save space and draw examples quicker, one can omit the "information" part, hence reducing the dynamic dictionary abstract data type (ADT) to a dynamic set ADT. This generates some minor technical differences:
A. inserting the pairs (10,A), (20,B), (30,C) in a dictionary (2,3) Tree yields a tree of height 1, with the pair of keys (20,30) at the ternary root separating 3 leaves coding for the 3 pairs (10,A), (20,B), (30,C); while
B. inserting the keys 10,20,30 in a set (2,3) Tree yields a tree of height 2, with a binary node (20) at the root, separating two binary nodes (10) and (30) [separating 4 empty leaves, if this makes any sense].
I find solution B a bit confusing to me (albeit I can cope with that) but, more importantly, confusing to undergraduate students, who end up learning how a search tree works without understanding why it works this way. I am wondering if it is an example of simplification making it (voluntarily) more complicated, or if there are reasons (e.g. practical applications) to study search trees with information (or pointers to information) along with the search keys in the internal node.
Notes: Obviously enough,
- Splay trees SHOULD have the information (or pointer to it) along with the search keys in the node; and
- any search tree optimizing memory accesses (such as B-Trees) should have all information in the leaves in order to minimize paging while navigating the internal nodes.