What is a 2-4 Tree ?
A 2-4 Tree is a self-balancing tree that has logarithmic insertion, deletion, and search operations (with the important distinction that the best-case for search is O(1).
Properties of a 2-4 Tree
It can be useful to make a distinction between structural properties and ordering properties when talking about data structures.
Structural Properties
- A 2-4 tree is a multi-way tree where each node has 2 to 4 children. (Thus, each node has 1 to 3 elements.) (Each element within a node has a left child node and a right child node.)
- Each null reference must be at the same depth in the tree. (Thus, all leaf nodes are at the same depth.) (Note: Having all leaf nodes at the same depth does not necessarily guarantee that all null references are at the same depth!)
Ordering Properties
- The values within each node are in sorted order.
- For each value in the tree, the following properties hold: all the values in its left subtree are less than it, and all the values in its right subtree are greater than it. (If duplicates are allowed, you just have to decide whether you always go left or always go right in the case where you encounter equal values.)
Insertion into a 2-4 Tree
Insertion is always done from the leaf nodes.
- Perform a BST-style traversal to find where to place the element. Insert into that node in sorted order.
- If an element causes an overflow (i.e., the node we’re trying to insert into would end up with 4 values), perform a squish-up operation (a.k.a. “splitting”).
- While squishing up causes overflow at the parent node, continue to squish up.
Deletion from a 2-4 Tree
The deletion operation can get pretty complex. All of the interesting cases for deletion revolve around leaf node deletion.
-
When deleting a non-leaf element, replace it with the maximum value from the left subtree. (Alternatively, we could have chosen the minimum value from the right subtree, but we have established the max value from left subtree approach as our standard practice for the rest of the semester and on all exams.)
- Counterintuitively, step (1) is probably the trickiest part of 2-4 deletion, because it’s so easy to get caught up in the deletion game and think that you need to transfer or fuse-and-drop instead of kicking things off with this BST-style replacement.
-
If deleting an element from a leaf node with multiple elements, just remove it, and we’re finished.