Balanced Search Trees - Data Structures and Abstractions with Java - page 707

FIGURE 27-17

The 2-3 tree after adding 35

60

20 50

80

10 35 40 55 70 90

Compare the final 2-3 tree in Figure 27-17 with the AVL tree in Figure 27-10a. We used the
same sequence of additions to form both trees. The 2-3 tree is completely balanced and shorter than
the balanced AVL tree. Later, we will compare these trees with the 2-4 tree in the next section and
draw some conclusions.

Splitting Nodes During Addition
27.20

Splitting a leaf. During the addition of a new entry to a 2-3 tree, the first node that splits is a leaf
that already contains two entries. Figure 27-18a shows a leaf that would need to accommodate
three entries. These entries are shown in ascending order as s , m , and l : s is the smallest entry in the
node, m is the middle entry, and l is the largest. The node splits into two nodes that contain s and l ,
respectively, and the middle entry m moves up a level. If the parent of the leaf has room for m , no
further action is necessary. This is the case in Figure 27-18a. But in Figure 27-18b, the parent
already contains two entries, so we must split it as well. We consider that case next.
Although Figure 27-18 shows the leaf as a right child of its parent, other analogous configura-
tions are possible.

FIGURE 27-18

Splitting a leaf to accommodate a new entry when the leaf's
parent contains (a) one entry; (b) two entries

(a)

p m

p Parent

Split

p m

s m l

s

l

(b)

p q p q m Parent must split

Parent

Split

p m

s m l s m l

s

l

27.21

Splitting an internal node. You just saw that splitting a leaf can cause the leaf's parent to have too
many entries. This parent also has too many children, as illustrated in Figure 27-18b. Figure 27-19
shows such an internal node in general. This node must accommodate three entries s , m , and l ,
given in ascending order, and four children that are the roots of the subtrees T 1 through T 4 . Thus,