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

we split the node, move the middle entry m up to the node's parent, place s and l into their own
nodes, and distribute the original node's subtrees between s and l . If the parent has room for m , no
further splitting is necessary. If not, we split the parent as just described.
Other analogous configurations for an internal node are possible.

FIGURE 27-19

Splitting an internal node to accommodate a new entry

m

Split

s

s m l l

T 1 T 2 T 4 T 1 T 2 T 3

T 3 T 4

27.22

Splitting the root. Splitting a root proceeds just like the previous cases, except that when we move
an entry up a level, we allocate a new node for the entry. This new node becomes the root of the
tree, as Figure 27-20 illustrates. Notice that only this case increases the height of a 2-3 tree.

FIGURE 27-20

Splitting the root to accommodate a new entry

m

Split

s m l s

l

T 1 T 2 T 4 T 1 T 2 T 3

T 3 T 4

Question 13 What tree results when you add 30 to the 2-3 tree in Figure 27-17?
Question 14 What 2-3 tree results when you make the following additions to an initially
empty 2-3 tree? 70, 80, 90, 20, 10, 50, 60, 40, 30

Question 15 How does the tree that you created in the previous question compare to the
AVL tree you created in Question 7?

2-4 Trees

27.23

A 2-4 tree , sometimes called a 2-3-4 tree , is a general search tree whose interior nodes must have
either two, three, or four children and whose leaves occur on the same level. In addition to 2-nodes
and 3-nodes, as we described in the previous section, this tree also contains 4-nodes. A 4-node con-
tains three data items s , m , and l and has four children. Data that is less than the smallest data item s