License: GPL2
nary-tree
The n-ary-tree package implements an automatically rebalancing B-tree data structure which supports n >= 5 items in any mixture of types per node. By storing multiple items per node, per-item memory overhead is decreased and searches are potentially made more efficient. This is done by increasing the distance traversed over the search space with each step since the number of nodes discarded is multiplied by the number of items per node. Duplicate items are allowed and items are always maintained in sort order. The user must supply a sort function, a key calculation function and optionally, an equality test function. By allowing the user to define the characteristics of the key values, the N-ARY tree allows the user to implement ordering in a convienent & hopefully efficient manner.