Java Reference
In-Depth Information
18
33
12
23
30
48
10
15
20
21
24
31
45
47
50
52
Figure10.9
A 2-3 tree.
leads to the B-tree of Section 10.5, which is by far the most widely used indexing
method today.
10.4
2-3 Trees
This section presents a data structure called the 2-3 tree. The 2-3 tree is not a binary
tree, but instead its shape obeys the following definition:
1. A node contains one or two keys.
2. Every internal node has either two children (if it contains one key) or three
children (if it contains two keys). Hence the name.
3. All leaves are at the same level in the tree, so the tree is always height bal-
anced.
In addition to these shape properties, the 2-3 tree has a search tree property
analogous to that of a BST. For every node, the values of all descendants in the left
subtree are less than the value of the first key, while values in the center subtree
are greater than or equal to the value of the first key. If there is a right subtree
(equivalently, if the node stores two keys), then the values of all descendants in
the center subtree are less than the value of the second key, while values in the
right subtree are greater than or equal to the value of the second key. To maintain
these shape and search properties requires that special action be taken when nodes
are inserted and deleted. The 2-3 tree has the advantage over the BST in that the
2-3 tree can be kept height balanced at relatively low cost.
Figure 10.9 illustrates the 2-3 tree. Nodes are shown as rectangular boxes with
two key fields. (These nodes actually would contain complete records or pointers
to complete records, but the figures will show only the keys.) Internal nodes with
only two children have an empty right key field. Leaf nodes might contain either
one or two keys. Figure 10.10 is an implementation for the 2-3 tree node.
Note that this sample declaration does not distinguish between leaf and internal
nodes and so is space inefficient, because leaf nodes store three pointers each. The
techniques of Section 5.3.1 can be applied here to implement separate internal and
leaf node types.
