Java Reference
In-Depth Information
18
33
12
23
30
48 52
10
15
20
21
24
31
45
47
50
55
Figure10.13
A simple node-splitting insert for a 2-3 tree. The value 55 is added
to the 2-3 tree of Figure 10.9. This makes the node containing values 50 and 52
split, promoting value 52 to the parent node.
record to be inserted without further concern for which two were already in L and
which is the new record. The first step is to split L into two nodes. Thus, a new
node — call it L
0
— must be created from free store. L receives the record with
the least of the three key values. L
0
receives the greatest of the three. The record
with the middle of the three key value is passed up to the parent node along with a
pointer to L
0
. This is called a promotion. The promoted key is then inserted into
the parent. If the parent currently contains only one record (and thus has only two
children), then the promoted record and the pointer to L
0
are simply added to the
parent node. If the parent is full, then the split-and-promote process is repeated.
Figure 10.13 illustrates a simple promotion. Figure 10.14 illustrates what happens
when promotions require the root to split, adding a new level to the tree. In either
case, all leaf nodes continue to have equal depth. Figures 10.15 and 10.16 present
an implementation for the insertion process.
Note that
inserthelp
of Figure 10.15 takes three parameters. The first is
a pointer to the root of the current subtree, named
rt
. The second is the key for
the record to be inserted, and the third is the record itself. The return value for
inserthelp
is a pointer to a 2-3 tree node. If
rt
is unchanged, then a pointer to
rt
is returned. If
rt
is changed (due to the insertion causing the node to split), then
a pointer to the new subtree root is returned, with the key value and record value in
the leftmost fields, and a pointer to the (single) subtree in the center pointer field.
This revised node will then be added to the parent, as illustrated in Figure 10.14.
When deleting a record from the 2-3 tree, there are three cases to consider. The
simplest occurs when the record is to be removed from a leaf node containing two
records. In this case, the record is simply removed, and no other nodes are affected.
The second case occurs when the only record in a leaf node is to be removed. The
third case occurs when a record is to be removed from an internal node. In both
the second and the third cases, the deleted record is replaced with another that can
take its place while maintaining the correct order, similar to removing a node from
a BST. If the tree is sparse enough, there is no such record available that will allow
all nodes to still maintain at least one record. In this situation, sibling nodes are
