### 2-3-Trees

 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.Allison

```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:
 The Darwin Awards V: Next Evolution

 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 Tuesday, 25-Oct-2016 05:19:04 EST.