申論題

10. (3 points) A red-black tree is a binary tree where every node has a color (red or black), and has the following properties.
1. The root is black.
2. All paths from the root to a leaf have the same number of black nodes.
3. Every red node must have two black children.
 For ease of discussion we assu sume that all null pointers (a special pointer to "nothing") point to a special black node. As a result all counting of the second property ends at this special node.
 1. If we do not guarantee the first property, but still guarantee the second and the third properties, we will not be able to guarantee that the height of the tree is O(logn).
2. It is possible that there are no red nodes in a red-black tree of 100000 nodes.
3. We insert a key k into a non-empty red-black tree just like into an ordinary binary search tree as a leaf, attach to it two null pointers to the special black node, and then immediately stop without any adjustment. If we color k red, we may violate the second property above.
 4. Consider the scenario above. If we color k red, we may violate the third property above.
5. Consider the scenario above. If we color k black, we will violate the second property above.