Chapter 19 Questions
Multiple Choice
1. If you use a binary search tree to implement an ADT dictionary, when does the efficiency of this
implementation suffer?
a. when the tree loses its balance
b. when the tree is too balanced
c. when the data portions of the nodes are too large
d. when a node accidentally has three branches
2. What is sensitive to the order of additions to and removals from a binary tree?
a. the contents of the nodes
b. the height of the tree
c. the complexity of the links
d. the implementation of the binary tree
3. A binary tree is considered balanced if the heights of its two subtrees differ by
a. at least 1
b. exactly 1
c. at most 1
d. zero
4. You can traverse a 2-3 tree in sorted order by performing the analogue of a(n) _______ traversal
on a binary tree.
a. pre-order
b. post-order
c. tri-order
d. in-order
5. A 2-3 tree with n nodes cannot be taller than
a. log2(n + 1)
b. log2(n)
c. n + 1
d. 2n + 1
6. A 2-3 tree implementation of a dictionary is of what efficiency for all its operations?
a. O(log2(n + 1))
b. O(log n)
c. O(n)
d. O(n + 1)
7. In a 2-3-4 tree, how many data items must a node have if it has 4 children?
a. 2
b. 3
c. 4
d. 5
Chapter 19 Questions
8. A red-black tree has the advantages of a 2-3-4 tree …
a. but requires more storage
b. and requires the same amount of storage
c. but requires less storage
d. but is less complicated
9. What distinguishes the root of a red-black tree?
a. it is red
b. it is either red or black, but will have 4 children
c. it is either red or black and has exactly 1 child
d. it is black
10. When working with a red-black tree, splitting nodes involves color pointer changes, called
rotations. What does this do to the tree?
a. shorten the tree
b. lengthen the tree
c. keeps it the same length
d. reverses the tree
Chapter 19 Questions
True or False
1. The efficiency of using a binary search tree to implement an ADT dictionary suffers when the
tree loses its balance.
2. Numerous additions to and removals from a binary search tree will invariably destroy its balance.
3. You can search an AVL tree almost as efficiently as a minimum height binary search tree.
4. An AVL tree implementation of a dictionary is of equal difficulty to other implementations.
5. It can be proven that the height of an AVL tree with n nodes will always be very close to the
theoretical minimum of log2(n + 1).
6. A 2-3 is pretty much the same as a binary tree.
7. A 2-3 tree is never taller than a minimum-height binary tree.
8. The leaf of a 2-3 tree must contain exactly 2 data items.
9. Searching a 2-3 tree is efficient.
10. Searching a 2-3 tree is more efficient than searching a binary search tree.
11. According to the text, maintaining the shape of a 2-3 tree is relatively easy.
12. A 2-3-4 tree requires the same amount of storage as a 2-3 tree.
13. The algorithms for adding data to and removing data from a 2-3-4 tree require fewer steps than
those for a 2-3 tree.
14. Every red node of a red-black tree has a black parent and a red child.
15. Every path from the root to a leaf in a red-black tree contains the same number of black nodes
Chapter 19 Questions
Short Answer
1. What is an AVL tree (not what do the initials stand for)?
2. What restores the balance of an AVL tree?
3. What two operations do not change the structure of an AVL tree and proceed just as they would
for an unbalanced binary search tree?
4. In what situation is a binary tree considered balanced?
5. The node N of a subtree itself has two subtrees. The left subtree has height 4, the right subtree
has height 6. What is the balance factor of node N?
6. A 2-3 tree is a tree in which each internal node has either ______ or ______ children and all
leaves are at the same level.
7. Specify the values of two possible data items that could be in the empty node of this 2-3 tree.
8. What is the efficiency of searching a 2-3 tree?
Chapter 19 Questions
9. Specify the value of the data item that could be in the empty node of this 2-3-4 tree.
10. You are searching or traversing a red-black tree. You can use the binary search tree algorithm,
but what do you do with the color pointers?