Java Reference
In-Depth Information
C
HAPTER
S
UMMARY
•
An AVL tree is a balanced binary search tree that rearranges its nodes whenever it becomes unbalanced. If
adding a node causes an imbalance, one single or double rotation restores the tree's balance.
•
A 2-node is a node that has two children and one data item. A 3-node has three children and two data items.
•
A 2-3 tree is a balanced search tree that contains 2-nodes and 3-nodes. When an addition to the tree would
cause a leaf to have three data items, the leaf splits into two 2-nodes. These nodes contain the smallest and
largest of the three data items and become the children of the former leaf's parent. The middle data item
moves up to this parent node, possibly causing the node to split.
•
A disadvantage of the 2-3 tree is that the addition algorithm follows a path from the root to a leaf and then
returns along that path as nodes split.
•
A 4-node has four children and three data items.
•
A 2-4 (or 2-3-4) tree is a balanced search tree that contains 2-nodes, 3-nodes, and 4-nodes. During an addi-
tion to the tree, each 4-node is split as it is considered during the search from root to leaf. Thus, returning
along the path to the root is unnecessary.
•
A red-black tree is a binary search tree that is logically equivalent to a 2-4 tree. Conceptually, a red-black
tree is more involved than a 2-4 tree, but its implementation is more efficient because it uses only 2-nodes.
•
Additions to a red-black tree maintain the tree's balance and status as a red-black tree by using color flips as
well as rotations like those used for an AVL tree.
•
A
k
-node is a node that has
k
children and
k
-
1 data items.
•
A multiway search tree of order
m
is a general tree that contains
k
-nodes for values of
k
ranging from 2 to
m
.
A B-tree of order
m
is a balanced multiway search tree of order
m
. To maintain its balance, a B-tree requires
every interior node to have a certain number of children and has all its leaves on the same level.
•
A 2-3 tree is a B-tree of order 3; a 2-4 tree is a B-tree of order 4.
•
A B-tree is useful when data is maintained in external storage, such as a disk.
E
XERCISES
1.
Implement the algorithm for a left-right double rotation, as given in Segment 27.5.
2.
Add 62 and 65 to the AVL tree in Figure 27-27a.
3.
Add 62 and 65 to the 2-3 tree in Figure 27-27b.
4.
Add 62 and 65 to the 2-4 tree in Figure 27-27c.
5.
Add 62 and 65 to the red-black tree in Figure 27-29.
6.
Each of the trees in Figures 27-27 and 27-29 contains the same values. Exercises 2 through 5 asked you to add 62
and 65 to each of them. Describe the effect that these additions had on each tree.
7.
What red-black tree is equivalent to the 2-4 tree in Figure 27-25b?
