[prev] 99 [next]

2-3-4 Trees (cont)

2-3-4 tree searching cost analysis:
  • as for other trees, worst case determined by height h
  • 2-3-4 trees are always balanced ⇒ height is O(log n)
  • worst case for height: all nodes are 2-nodes
    same case as for balanced BSTs, i.e. h ≅ log2 n
  • best case for height: all nodes are 4-nodes
    balanced tree with branching factor 4, i.e. h ≅ log4 n