2-3-4-Trees

A 2-3-4-tree is a generalisation of a [2-3-tree].

1. nil is a 2-3-4 tree,
2. a leaf is a 2-3-4 tree,
3. a fork has either 2, 3 or 4 children,
4. all paths from the root to a leaf are of equal length i.e a 2-3-4-tree is height-balanced

An interior fork-node has the following structure:

    |, k1, |, k2, |, k3,|
    |      |      |     |
    |      |      |     |
    |      |      |     v
    |      |      v     child4
    |      v      child3
    v      child2
    child1

k1 is the key of the least element in child2.
k2 is the key of the least element in child3 (if present).
k3 is the key of the least element in child4 (if present).

The keys in fork nodes are used to determine which subtree to descend when searching and inserting. When a new element is added, it may make the parent fork-node full. If the parent is already full, it can be split, rather as for [2-3-trees], and splits may propagate farther up the tree.

An alternative method (e.g. Sedgewick 1990 p216) is to split any 4-nodes encountered during the descent of the 2-3-4-tree.

---->[|, |]                               --->[|, |, |]
      |  |                                     |  |  |
      |  |                                     |  |  |
      |  |                                     |  |  [|, |]
      T  [|, |, |, |]    -- 4-node             T  |   |  |
          |  |  |  |                              |   |  |
          |  |  |  |                              |   C  D
          |  |  |  |                              |
          A  B  C  D                              |
                                                  [|, |]
                                                   |  |
                                                   |  |
                                                   A  B

      Before                                     After

There may still be 4-nodes after this process, e.g.

---->[|, |, |]                             --->[|, |, |, |]
      |  |  |                                   |  |  |  |
      |  |  |                                   |  |  |  |
      |  |  |                                   |  |  |  [|, |]
      T  U  [|, |, |, |]  -- 4-node             T  U  |   |  |
             |  |  |  |                               |   |  |
             |  |  |  |                               |   C  D
             A  B  C  D                               |
                                                      |
                                                      [|, |]
                                                       |  |
                                                       |  |
                                                       A  B

      Before                                     After

This means that insertion has only "local" effects; no further action is necessary, higher up the 2-3-4-tree, after a new element has been added. It can be thought of as a 2-3-tree where the over-full (3+1)-nodes are not split immediately, but rather exist for a time as 4-nodes, and are split during some later insertion(s).

Notes

• Many variations are possible, e.g.
  • elements are only placed in leaf nodes, as above in which case forks are "indexes", or
  • elements are placed in forks and also in leaf nodes, as in Sedgwick 1990.
• R. Sedgewick. Algorithms in C. Addison Wesley 1990, top-down 2-3-4-trees, p216.
  Also shows how to represent a 2-3-4-tree as a binary tree with one extra bit per fork-node to indicate whether the link to a node is "red" or "black": 3-nodes are represented as two binary-tree nodes joined by a "red"-link. 4-nodes are represented by three binary-tree nodes joined by two "red"-links. "Normal" links in the 2-3-4-tree are represented as "black"-links in the binary tree.
• See also [2-3-trees], and [B-trees] a generalisation of 2-X-trees.