aud.A234Tree< Key extends Comparable Class Template Reference

Simple implementation of 2-3-4-trees based on KTreeNode. More...

Detailed Description

Simple implementation of 2-3-4-trees based on KTreeNode.

Note that in contrast to BinarySearchTree ...

• we store only keys rather than key-value pairs.
• there is no dummy node head, there is no reference to parents.

The class implements insertion with top-down and bottom-up splits. The strategy for splitting is selected at construction.

• In top-down mode, insert calls the recursive insert_top_down, which splits all 4-nodes (using split_top_down) on the way down to the insertion position. (This may split the root!) So the final KTreeNode#insert is guaranteed to not cause a split.
• In bottom-up mode, insert calls the recursive insert_bottom_up, which inserts first and splits if the new node is a 5-node (recursive split_bottom_up).
  Note that this is sort of cheating for ease of implementation because in a proper 2-3-4-tree, there cannot be 5-nodes! (We use KTreeNode.) This has the side effect, that the selection of the node that is "pulled up" to the parent by KTreeNode#mergeChild) possibly has to be "corrected" if the insertion position was less than 2.

Note that there is currently no operation for removal. (This would cause KTreeNode#mergeChild.)

Definition at line 38 of file A234Tree.java.

---

The documentation for this class was generated from the following file:

• A234Tree.java