# 2-3-4 Tree

src:
https://sedgewick.io/talks/#ll-red-black-trees

Used in:Red Black Tree Left Leaning Red Black Tree

## # 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

**Search**to bottom for key- If its a 2-node: convert it to 3-node
- If its a 3-node: convert it to 4-node.
- If its a 4-node:
- move the middle key to parent
- split remainder to two 2-node
- 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

- 4-node below 2-node
- 4-node below a 3-node

## # Conclusion

Too complex for implementation

Enhancement: Left Leaning Red Black Tree