|
- nil is a 2-3 tree,
- a leaf is a 2-3 tree,
- a fork has either 2 or 3 children (subtrees),
- 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:
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.
|
|