Formal Definition of DodekaTrie

As stated earlier, you will be implementing the SortedMap using a Sevem-ary search trie (DodekaTrie). A DodekaTrie would be similar to a B+ tree of order 12. So, the definition is usually implemented as an m-ary tree, where the degree of the root of any subtree is m, and leaf nodes do not have any space reserved for children⁵.

To facilitate exhaustive testing, you will implement a DodekaTrie using a version of the schema for B+ trees, with the branching factor fixed at 12. We have a parameter, leafOrder, which is the (max) number of keys that can fit in a leaf of an DodekaTrie. This is needed because there is no restriction that the size of the leaf node must match the size of an internal (guide) node; so, the number of keys in a DodekaTrie leaf node can be any number greater than or equal to one.

Your DodekaTries must be constructed using the following rules and conventions; no exceptions can or will be made.

• The root is either a leaf with at least one key, or has at least two non-empty child subtrees.
• Internal nodes: must have exactly seven child subtrees per node, at least four of which are not empty. Thus, each internal node contains at least three guide values at all times.

• All leaves of the DodekaTrie must be at the same level.

• Leaf nodes must contain at least $\lceil \frac{leafOrder}{2} \rceil$ and $leafOrder$ (non-null) keys, inclusive.

• Actual search keys (leaf data) must be unique. However, no such restriction exists within the set of acceptable guide values, and guide values may match keys. So, to accommodate such data value replication, we adopt the convention that a guide (internal node data value) must be greater than the data values (guide or key) in the nodes to the left and below it. A guide (internal node data value) must be less that or equal to the data values (guide or key) in the node to the right of it and below it. This is a version of the 12-way search tree/trie property. There are no other rules regarding the selection of guide values (!).

These rules ARE mandatory, meaning that no credit will be given for the DodekaTrie if these rules are not observed. Just like the binary heap, there can be multiple DodekaTries of a given order that are correct. Since grading by merely diff-ing is impossible, we will grade your DodekaTrie by checking that the structure you produce satisfies the above rules.