（红黑树上的连接操作）连接（join）操作取两个动态集合S1,S2和一个元素x，使得对任何
。该操作返回一个集合
。在这个问题中，讨论如何在红黑树上实现连接操作。
a.给定一棵红黑树T，其黑高被存放在新属性T.bh中。证明：在不需要树中节点的额外存储空间和不增加渐近运行时间的前提下，RB-INSERT和RB-DELETE可以维护这个属性。并证明：当沿T下降时，可以对每个被访问的节点在O(1)时间内确定其黑高。
要求实现操作RB-JOIN(T1,x,T2)，它销毁T1和T2并返回一棵红黑树
，设n为T1和T2中的节点总数。
b.假设
。试描述一个O(lgn)时间的算法，使之能从黑高为T2.bh的节点中选出具有最大关键字的T1中的黑节点y。
c.设Ty是以y为根节点的子树。试说明如何在不破坏二叉搜索树性质的前提下，在O(1)时间内用
来取代Ty。
d.要保持红黑树性质1,3和5，应将x着成什么颜色？试说明如何在O(lgn)时间内维护性质2和性质4。
红黑树性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点
e.论证使用（b）部分的假设是不是一般性的，并描述当
时所出现的对称情况。
f.证明：RB-JOIN的运行时间是O(lgn)。
