In the style of Figure 13.1(a), draw the complete binary search tree of height 3 on the keys {1, 2, ..., 15}. Add the NIL leaves and color the nodes in three different ways such that the black-heights of the resulting red-black trees are 2, 3, and 4.
因为是一颗完全二叉树，超级平衡，所以填色很容易. 感谢psu提供的图片
Draw the red-black tree that results after TREE-INSERT is called on the tree in Figure 13.1 with key 36. If the inserted node is colored red, is the resulting tree a red-black tree? What if it is colored black?
插入后如果上红色，那么违反了红节点的儿子节点是黑色这个规则.
插入后如果上黑色，那么违反了路径上包含相同黑节点数这个规则.
English:
Node is Red: This is not a Rid-Black tree, because after every red node, the children must be black. Hence, a red 36 would break the tree's properties.
Node is Black: This alters the Black-height of the tree. However, all the other simple paths have their old Black-height. This breaks the property of the Red-Black tree, and thus it is not a Red-Black tree.
To add anything to a tree, the tree needs to be re-arranged and re-painted each time to match its properties.
Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. If we color the root of T black but make no other changes to T, is the resulting tree a red-black tree?
当然还是～
Suppose that we "absorb" every red node in a red-black tree into its black parent, so that the children of the red node become children of the black parent. (Ignore what happens to the keys.) What are the possible degrees of a black node after all its red children are absorbed? What can you say about the depths of the leaves of the resulting tree?
- 2, 如果该节点的两个子结点都是黑的.
- 3, 如果仅有一个子结点是红的.
- 4, 如果两个子结点都是红的.
所有的叶子节点都有相同的高度.
Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.
根据性质5，最长和最短路径都有相同的黑节点数. 根据性质4可知路径上红节点数目不会超过黑节点，可得.
English:
For example, let's give a Red-Black Tree the black-height of 3. The shortest simple path would be: 3 black nodes in line.
The longest simple path would be: 3 black nodes + 3 red nodes. Every red node must have a black child, and we give every black node a red child to maximize the red children we have on the path.
In total, the lenght of the shortest possible path for black-height 2, is 3 nodes. The longest possible path is 6 nodes, which is twice, possibly less but never more, than the amount of nodes on the shortest simple path.
What is the largest possible number of internal nodes in a red-black tree with black-height k? What is the smallest possible number?
只有一条全黑 path 的情况下, 节点数最小, 是k.
The smallest possible number of internal nodes is when there is only one path of all black nodes, which contains k nodes.
假如是一黑一红交替，那么总高度就是2k-1. 这种情况下, 节点数最大, 是
The largest possible number of internal nodes is . It occurs when every other node in each path is a black node. This is produced by a complete binary tree which has alternating levels of black and red nodes. Since the black height is k, the height of the tree is 2k.
Describe a red-black tree on n keys that realizes the largest possible ratio of red internal nodes to black internal nodes. What is this ratio? What tree has the smallest possible ratio, and what is the ratio?
- 最大的比值是2，根节点是黑色，两个子节点是红色.
- 最小的比值是0，比如只有一个黑色的根节点.
Follow @louis1992 on github to help finish this task.