# 2-3-4 Tree

Aug 19, 2022

## # Definition

• Node
• 2-node = 1 key 2 children
• 3-node = 2 key 3 children
• 4-node = 3 key 4 children
• Child
• Left child = less than key.0
• Middle.0 child = between key.0 and key.1
• Middle.1 child = between key.1 and key.2
• Right child = greater than key.2

## # Operation

• Search

• Insert

1. Search to bottom for key
2. If its a 2-node: convert it to 3-node
3. If its a 3-node: convert it to 4-node.
4. If its a 4-node:
1. move the middle key to parent
2. split remainder to two 2-node
3. goto: 2
• Problem here, parent may be 4-node
• Solution 1: Use the same method to split parent, then continue up the tree if necessary. (Bottom up, like RBTree-FixUp)
• Solution 2: Split 4-nodes on the way down, insert at bottom. (Top down)
• Splitting 4-nodes on the way down
• Put the middle to the up right
• 4-node below a 4-node case never happens
• Bottom node reached is always a 2-node or a 3-node
1. 4-node below 2-node
2. 4-node below a 3-node

## # Conclusion

Too complex for implementation
Enhancement: Left Leaning Red Black Tree