Teaching (2,3) and AVL Trees: information in internal nodes or in external nodes?

Question

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,

1. Splay trees SHOULD have the information (or pointer to it) along with the search keys in the node; and
2. 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.

Answer 1

I think the two situations are entirely different in applications. In the case that the internal nodes are only search keys we find applications in database indices. By associating keys with internal nodes we obtain space efficient dictionary types.

The contrast between the two cases could help learners understand the concepts more easily. By focusing on the differences between the two cases, perhaps without too much reference to the implementation of the tree operations themselves, learners would better understand the utility of the datatype.

Once that is the case you could choose either case to explore the operations in more detail. Or why not be groovy and use red/black trees. As a student I found AVL and 2-3 tree theory deeply boring whereas red/black trees were quite exciting. I think because the rules are so much more interesting, involving colours rather than arithmetic.

As a teacher I have always regarded me being confused as a sure sign that my learners will be. Perhaps more visuals would help out - and that means colours - and those tree rotations are beautiful!

I would also say that such things are not really confusing - its just how they work out - like music, its just that way. Similarly AVL trees and 2-3 trees being the data type analogue of Manhatten Transfer are less inspiring to a modern audience than https://www.youtube.com/watch?v=HZfnmNf5MwA.

What you say about splay trees, and the finer implementation details of B+tree indices is correct, but who really cares - not your students - they are already confused. Give them some colours, give them a taste of the good stuff and ... then start looking at 2-3 trees, I mean, when you are no longer bored, confused and not listening - but instead - curious and inspired, those 2-3 trees ... well are they Fibonachi? I mean, thats better than dyadic surely ....

Answer - its best if your students are still awake after 10 minutes, ;)