2-3-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
  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

The root is now full and has to be split at the next insertion (of 30):

[|,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
The time to search, insert or delete is O(log n).

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.


© 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 Monday, 21-Apr-2014 09:27:34 EST.