
 nil is a 23 tree,
 a leaf is a 23 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 23tree is heightbalanced
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 23tree:
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 "overfull"
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 23 tree grows by 1.
1+log_{3}n <= height(n) <= 1+log_{2}n
The time to search, insert or delete is O(log n).
Implementation
Each interior node is like a miniindex.
During search, the keys are used to select which
subtree to explore.
A suitable Pascal datastructure
to implement a 23 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
 [234trees] and
[Btrees]
are generalisations of 23trees.
 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.

