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

You saw in Segment 25.42 of Chapter 25 that searching a balanced binary search tree, such as
an AVL tree, is an O(log n ) operation. Since 2-3 and 2-4 trees are no taller than a corresponding
AVL tree, we usually can search them by examining fewer nodes. However, 3-nodes and 4-nodes
contain more entries than 2-nodes, and so they require a longer search time. In general, searching
an AVL, 2-3, or 2-4 tree is an O(log n ) operation.
A 2-3 tree is appealing because maintaining its balance is easier than for an AVL tree. Main-
taining the balance of a 2-4 tree is even easier. But defining search trees whose nodes contain more
than three data items is usually counterproductive, because the number of comparisons per node
increases. As you will see later in this chapter, such a search tree is attractive when it is maintained
in external storage, such as a disk, instead of internal memory.

Red-Black Trees

27.31

You just saw that maintaining the balance of a 2-4 tree is easier than maintaining either an AVL tree
or a 2-3 tree. While a 2-4 tree is a general tree, a red-black tree is a binary tree that is equivalent to
a 2-4 tree. Adding an entry to a red-black tree is like adding an entry to a 2-4 tree, in that only one
pass from root to leaf is necessary. But a red-black tree is a binary tree, so it uses simpler operations
to maintain its balance than does a 2-4 tree. Additionally, the implementation of a red-black tree
uses only 2-nodes, whereas a 2-4 tree requires 2-nodes, 3-nodes, and 4-nodes. This added require-
ment of a 2-4 tree makes it less desirable than a red-black tree.

Note: A red-black tree is a binary tree that is equivalent to a 2-4 tree. Conceptually, a red-
black tree is more involved than a 2-4 tree, but its implementation uses only 2-nodes and so is
more efficient.

27.32

When designing a node for the 2-4 tree, you need to decide how to represent the entries that are in
the node. Since you must order these entries, you could use an ADT such as the sorted list for the
entries. You might also use a binary search tree. For example, consider the 2-4 tree in Figure 27-27c.
The entries in the root of this tree are 20, 50, and 80. We can represent these entries as a binary
search tree whose root is 50 and whose subtrees are 20 and 80. Likewise, the entries in the 3-node
leaf of this 2-4 tree are 35 and 40. We can represent these entries as one of two binary search trees:
One has 35 as its root and 40 as its right subtree; the other has 40 as its root and 35 as its left subtree.
Thus, we can convert all 3-nodes and 4-nodes to 2-nodes. The result is a binary search tree instead of
a 2-4 tree.
Each time we convert a 3-node or a 4-node to a 2-node, we increase the height of the tree.
We use color to highlight the new nodes that cause this increase in height. We use black for all
the nodes in the original 2-4 tree. Since we do not change the 2-nodes, they remain black in the
new tree.
Figure 27-28a shows how to represent a 4-node by using 2-nodes. The root of the resulting
subtree remains black, but we color its children. The traditional color is red. Our figures use blue
since that is our book's second color. Similarly, Figure 27-28b shows how to represent a 3-node by
using one of two different subtrees, each having a black root and a red child.
With this notation, we can draw the 2-4 tree in Figure 27-27c as the balanced binary search tree
in Figure 27-29. This binary search tree is called a red-black tree.

Question 20 What comparisons are made while searching the 2-4 tree in Figure 27-27c
and the equivalent red-black tree in Figure 27-29 for

a. 60 b. 55