##13.1红黑树的性质
#####13.1-1 对关键字集合{1...15}，分别画出黑高2、3、4红黑树。
答：见图：
图 1（第1,3行是黑的）黑高2，图2（第1,2，4行是黑的）黑高3，情况3黑高4。
#####13.1-2
按照Tree-insert，插入36后应该是35的右孩子。无论是红色还是黑色，都不符合红黑数的定义：
如果是红色，违背规则4：红结点的左右孩子都是黑的；
如果是黑色，违背规则5： 不是每条简单路径上黑色结点数目都一样了。
（所以，普通二叉搜索树的insert算法不能应用于红黑树。）
#####13.1-3
依然是红黑树。
#####13.1-4
（诡异的问题。。。）以图13-1为例：
可能的度：
如果两个孩子一黑一红，为3，如7吸收3；
如果两个孩子都是红，为4， 如38吸收35和39；
如果两个孩子都是黑，为2， 如21的子树（19吸收20后）；
所有叶子节点的深度最后是都一样的了。（因为每条路径都剩下黑结点，每个路径黑结点个数还都是一样的）
#####13.1-5 红黑树中，最长简单路径最多是最短的简单路径长度的2倍。
比较非形式化的证明，树的黑高记为bh，则树中__最短路径为bh__。根据红黑树的__性质4，树中最长的路径最多有2xbh的高度__。故证毕。
#####13.1-6 黑高为k的红黑树，内部结点最多几个最少几个？
最少：全是黑的；
最多：一层黑一层红；
#####13.1-7 n个结点的红黑树，红色结点与黑色结点个数最大和最小的比值?
最大：一层黑一层红，2；
最小：没有红，0；
##13.2 旋转
#####13.2-1 写出RIGHT-ROTATE的伪代码
代码见RIGHT-ROTATE pseudo code.
#####13.2-2
用数学归纳法？
#####13.2-3
a深度+1，b深度不变，c深度-1。
#####13.3-1
z着为黑色，虽然不破坏性质4，但是会破坏性质 5。
#####13.3-2
答：见图：
#####13.3-4 证明RB-INSERT-FIXUP永远不会将T.nil.color设为RED
答：纵观RB-INSERT和RB-INSERT-FIXUP，只有三处讲一个结点的颜色设置为红，分别是RB-INSERT里对z，和RB-INSERT-FIXUP里两处对z.p.p，都不可能设置的是nil结点。
#####13.3-5 证明插入n个结点的红黑树，如果n>1，则该树至少有一个红结点。
因为新插入的结点，在调用fixup前是红的；然后调用fixup后分为以下两种情况：
如果该插入的结点的父结点是黑色的，那么fixup里的循环走不到，fixup退出循环后只有一行Code，是将root设置成black，而新插入的结点不是root(n>1)，所以此时新插入的结点保持是红色的，结论成立；
如果新插入的结点的父结点是红色的，那么会执行fixup里的循环，而fixup循环一定会执行case3（执行到case 3就是退出循环之时），case3里有将z.p.p设置成红色的操作，所以至少一个红结点的结论依然成立；
证毕。
###-------- 思考题 ----------
13-1 持久动态集合（即Scala中unmutable collections）
a. 插入的话，改变从根节点到插入的结点的简单路径上的所有结点。
删除的话，分几种情况：
如果删除的结点没有孩子或者只有一个孩子，则改变从根节点到删除的结点的简单路径上的所有结点； （因为没有Parent,所以不用改动孩子）
如果删除的结点有两个孩子：
-若后继是其右孩子，则改变从其右孩子到根的所有结点，如图。
-若后继不是其右孩子，则改变从被删除结点到根结点简单路径上的所有结点。 如图。
b. 代码见Persistent_Tree.
c. 时间：o(logN)，空间：logN个TreeNode的空间。（logN的期望值是树高）
d. 如果有父节点指针，需要更新所有的结点。为O(N)。
e. 和普通红黑树一样，多了一些复制操作。