2-3-4 Trees
2-3-4 trees have variable-size nodes
- each node contains 1 ≤ n ≤ 3
Item s and n+1 subtrees
- ordering as for BST (e.g. all keys in leftmost subtree < smallest key in node)
- new values inserted at leaves; all leaves are at the same level
- tree grows upward from root via split-promote
|