2-3-Trees

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

An interior node has the following structure:

    |, k1, |, k2, |
    |      |      |
    |      |      v
    |      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 not empty).

Suppose the following data was to be inserted, in order, into an empty 2-3-tree:

L . A l l i s o n

10 20 15 30 25 40



|
|
|
10                  -- a leaf


[|,20,|,-,/]        -- need a fork
 |    |
 |    |
 |    20            -- child 2
 10                 -- child 1


[|,15,|,20,|]
 |    |    |
 |    |    |
 |    15   |
 10        20

[|,20,|,-,/]
 |    |
 |    |
 |    [|,30,|,-,/]
 |     |    |
 |     |    |
 |     20   30
 |
 |
 [|,15,|,-,/]
  |    |
  |    |
  10   15


[|,20,|,-,/]
 |    |
 |    |
  ... [|,25,|,30,|]
       |    |    |
       |    |    |
       20   25   30


[|,20,|,30,|]           -- the root is
 |    |    |            -- full again
 |    |    |
 |    |    [|,40,|,-,/]
 |    |     |    |
 |    |     30   40
 |    |
 |    |
 |    [|,25,|,-,/]
 |     |    |
 |     20   25
 |
 |
 [|,15,|,-,/]
  |    |
  10   15

Complexity

When a node is "over-full" it is split into 2 nodes (now with 2 children each) and the extra node is inserted into the parent, which might split in turn,... If the root is split, the height of the 2-3 tree grows by 1.

1+log3n <= height(n) <= 1+log2n

Implementation

Each interior node is like a mini-index. During search, the keys are used to select which sub-tree to explore.

A suitable Pascal data-structure to implement a 2-3 tree is:

type tree23 = ^ tree23node;

     nodetype = (leaf, fork);

     tree23node =
        record case t:nodetype of
           leaf:( e :elementtype );
           fork:( c1, c2, c3 :tree23;
                  k1, k2 :elementtype)
        end

Notes

• [2-3-4-trees] and [B-trees] are generalisations of 2-3-trees.
• See
  • Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley 1974, p149.
  • e.g. see M. A. Weiss, Data Structures and Algorithm Analysis in C, Addison Wesley, 1997.