[prev] [index] [next]

2-3-4 Trees

2-3-4 trees have variable-size nodes
  • each node contains 1 ≤ n ≤ 3 Items 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

[Diagram:Pics/trees/2-3-4-tree.png]