算法导论的一道思考题，红黑树的连接（用c语言实现）
连接操作以两个动态集合S1和S2和一个元素x为参数，使对任何x1属于S1和x2属于S2，有key[x1]<=key[x]<=key[x2]。该操作返回一个集合S=S1并{x}并S2。在这个问题中讨论如何在红黑树上实现连接操作。
我们希望实现操作RB-JOIN(T1,x,T2),它删除T1和T2，并返回一棵红黑树T=T1并{x}并T2。设n为T1和T2中的总节点数。
T1和T2的黑高度分别为bh[T1]和bh[T2]。
假设bh[T1]>=bh[T2]。要保持红黑性质1),3),5),应将x着什么颜色？说明如何在的时间内恢复性质2)、4)。


红黑性质：
1)每个结点是红的，或是黑的。
2)根节点是黑的。
3)每个叶节点(NIL)是黑的。
4)如果一个结点是红的，则它两个儿子都是黑的。
5)对每个结点，从该结点到其子孙叶节点的所有路径上包含相同数目的黑结点。
[解决办法]
先将节点x染为红色，判断T1和T2的黑高度，当bh[T1]=bh[T2]，则将T2作为x的右子树，T1作为左子树，将父节点设为NIL，x颜色改为黑色，这样两边黑高度一样，返回x即可；当bh[T1]>bh[T2]，从T1根节点开始向右寻找黑节点，从第bh[T1] - bh[T2] + 1个黑节点处截断，将该节点开始后面黑高度为bh[T2]的部分子树做为x的左子树，T2做为x的右子树，然后将该节点的父节点做为x的父节点，再返回T1即可；当bh[T1]<bh[T2],从T2根节点开始向左寻找黑节点，从第bh[T2] - bh[T1] + 1个黑节点处截断，将该节点开始后面黑高度为bh[T1]的部分子树做为x的右子树，T1做为x的左子树，然后将该节点的父节点做为x的父节点，再返回T2即可。这样就可以将两个红黑树连起来，并且各条路径黑高度都相等，不用再进行额外调整。思路理清，代码好办。