(also called B-tree of order 4)

why?

a lot of the cost associated with a binary search tree comes from traversing the tree

2-3-4 trees try to fix this by storing more data items per node and allowing up to 4 children per node (has $\log_4(n)$ rather than $\log_2(n)$)

structure

a 2-3-4 tree has one of 3 types of nodes:

• 2-nodes ⇒ 1 item + 2 children
• 3-nodes ⇒ 2 items + 3 children
• 4-nodes ⇒ 3 items + 4 children

the items within each node are sorted

❗️it is impossible to have a 3-node with only 2 children and 2 items, or a 4-node with < 4 children but 3 items

• sample code structure

rules

• the children to the left of the items in a node must be less than the items in the node
• the children between two items in a node must be between those two items
• the children to the right of the items in a node must be larger than the items in the node