 |
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
|
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
Node in a k-ary search tree. More...
Node in a k-ary search tree.
The implementation supports an arbitrary number of children/keys for each node, which are stored as entries (Entry) in a Vector.
Nodes support searching for an entry in the node and its subtrees, as inserting an entry into a node/subtree as well as splitting and merging nodes.
split splits a node in two halves and creates a new tree rooted by a 2-node, which stores the partitioning key.
mergeChild merges keys from a child into the parent node, i.e., "pulls up" the child.
Note that there are k-1 keys for k=getK children. The node always stores getK() entries where the leftmost (0-th) key is null by definition. (This way we store always pairs of keys and children in KTreeNode.Entry and avoid a special case.)
Different types of trees would use different strategies for splitting and merging. This way, KTreeNode serves as a basis for implementation of, e.g., 2-3-4 trees or B-trees. (The implementation is not efficient, similar notes as for BinarySearchTree apply)
In contrast to BinarySearchTree, the current implementation of KTreeNode stores only keys, there is no direct key-value mapping available.
Many method rely on correct input arguments. The implementation uses a lot of assertions but hardly explicit error checking (for the correct-use cases)! Make sure to run it with "-ea" when testing your code!
Definition at line 47 of file KTreeNode.java.
1.9.5