Insertion into 2-3-4 Trees (cont)
Variations on 2-3-4 trees …
Variation #1: why stop at 4? why not 2-3-4-5 trees? or M-way trees?
- allow nodes to hold up to M-1 items, and at least M/2
- if each node is a disk-page, then we have a B-tree (databases)
- for B-trees, depending on
Item size, M > 100/200/400
Variation #2: don't have "variable-sized" nodes
- use standard BST nodes, augmented with one extra piece of data
- implement similar strategy as 2-3-4 trees → red-black trees.
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}