1.Construct a red-black tree of height 2 with six elements. Construct a red-black tree of height 3 with six elements.
50
30 90
20 40 70
50
30 90
20 40
10
2.Construct two different red-black trees with the same three elements.
50
30 90
50
30 90
3.What is the maximum number of black elements in a red-black tree of height 4? What is the minimum number of black elements in a red-black tree of height 4?
The maximum number of elements will be attained for a full tree. By part 4 of the Binary Tree Theorem, a full binary tree of height 4 has 31 elements.
The minimum number of elements will be attained with all black elements, except for one root-to-leaf path with as many red elements as possible. For a height of 4, the maximum number of red elements in a path is 2, and the minimum number of elements is 10. For example,
50
30 90
20 40 80 100
10 25
15
4.It is impossible to construct a red-black tree of size 20 with no red elements. Explain.
A binary tree t with 20 elements cannot be full, so there are some elements that are leaves or have one child but are not at level height(t). This situation would violate the Path Rule if every element were black.
5.Suppose v is an element with one child in a red-black tree. Explain why v must be black and v’s child must be a red leaf.
If v’s child were black, the path from the root to v would contain at least one less black element than any path from the root through v’s child, and this situation would violate the Path Rule. So v’s child must be red. If v’s child were not a leaf, then – by the Red Rule – that grandchild of v must be black, but this situation would violate the Path Rule because the path from the root to v would contain at least one less black element than any path from the root through v’s grandchild. Therefore, v’s child must be a leaf. Finally, by the Red Rule, v must be black because v’s child is red.
6.Construct a red-black tree that (when the colors are ignored) is not an AVL tree.
50
30 90
20 40 80 100
10 25
15
This is a red-black tree whose left subtree has a height of 3 and whose right subtree has a height of 1, and so it is not an AVL tree.
7.Show the effect of making the following insertions into an initially empty TreeSet object:
30, 40, 20, 90, 10, 50, 70, 60, 80
By running the applet from Lab 20, the following red-black tree results:
50
30 70
20 40 60 90
10 80
8.Delete 20 and 40 from the TreeSet object in Exercise 7. Show the
complete tree after each deletion.
After removing 20:
50
30 70
10 40 60 90
80
After removing 40:
50
30 70
10 60 90
80
9. From a user’s point of view, what is the difference between the
TreeMap class and the TreeSet class?
Each element in a TreeMap object consists of a key-value pair. Each element in a TreeSet object consists of a key only.
10.From a developer’s point of view, what is the relationship between the
TreeMap class and the TreeSet class?
The TreeSet class has-a TreeMap field; the value field for each Entry object in the TreeMap field is ignored.