Java Reference
In-Depth Information
18
33
23
23
30
20
30
20
19
21
24
31
19
21
24
31
(A)
(B)
23
18
33
12
20
30
48
10
15
19
21
24
31
45
47
50 52
(C)
Figure10.14
Example of inserting a record that causes the 2-3 tree root to split.
(a) The value 19 is added to the 2-3 tree of Figure 10.9. This causes the node
containing 20 and 21 to split, promoting 20. (b) This in turn causes the internal
node containing 23 and 30 to split, promoting 23. (c) Finally, the root node splits,
promoting 23 to become the left record in the new root. The result is that the tree
becomes one level higher.
merged together. The delete operation for the 2-3 tree is excessively complex and
will not be described further. Instead, a complete discussion of deletion will be
postponed until the next section, where it can be generalized for a particular variant
of the B-tree.
The 2-3 tree insert and delete routines do not add new nodes at the bottom of
the tree. Instead they cause leaf nodes to split or merge, possibly causing a ripple
effect moving up the tree to the root. If necessary the root will split, causing a new
root node to be created and making the tree one level deeper. On deletion, if the
last two children of the root merge, then the root node is removed and the tree will
lose a level. In either case, all leaf nodes are always at the same level. When all
leaf nodes are at the same level, we say that a tree is height balanced. Because the
2-3 tree is height balanced, and every internal node has at least two children, we
know that the maximum depth of the tree is log n. Thus, all 2-3 tree insert, find,
and delete operations require (log n) time.
