2-3-4-Trees

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

Algorithms
 glossary
 Binary Trees
  Search T'
  23trees
  234trees
  Btrees
  Tries
  PATRICIA
  Suffix Trees

 Tables
C
o
m
p
u
t
e
r
-
S
c
i
e
n
c
e

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

but none of the 4-nodes can have another 4-node as parent!

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.


© L.A. 1986, Dept. Computer Science, Monash University, Australia 3168.
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 25-Dec-2014 11:52:51 EST.