如何判断一个二叉树能不能被染成红黑树
太长不看：如果一棵二叉树上每个点都满足：以其为根的子树的最长链长度不大于最短链长度二倍，那么它就可以被染成红黑树，否则就不行。换言之，能否染成红黑树与这一条件是充要关系。
一、首先给出一种判断的算法
1.1 一些约定
**最短链**：在以某个节点为根的子树中，从该节点出发到子树内的某个NIL结束的最短路径即为最短链，此链上的节点个数成为最短链长度（不包括NIL）。如果有若干条，每一条都是一个最短链。**黑需**：由于红黑树性质的要求，从某个节点出发到以这个节点为根的子树内的某个NIL结束的路径上需要有固定量的黑色节点，这个量我们称之为这个节点的黑需。为了方便证明，我们直接让整棵树的黑需等于整棵树的最短链长度，其可行性见**引理1**。
1.2 引理
**引理1** 如果一颗二叉树可以被染成红黑树，那么一定存在一种染色方法使得这棵树的最短链上的点全是黑色的，即该树的黑需就是该树的最短链长度。**证明**：考虑调整法。假如一颗二叉树可以被染成红黑树，那么对于任何一种染色方法，如果此时这棵树的最短链上的点有不是黑色的，我们可以把其中一个红点染成黑色，再把树中其他红点中的若干染成黑色，使得整棵树黑需+1。具体的染法思路为：当我们把某个点染成黑色时，那么以该点为根的子树内的所有链（即那些终点NIL在该子树内的链）都完成了黑点+1的任务。所以我们从顶向下检查，如果该点为红色，直接把该点染成黑色，它的子树内的任务都完成了。如果该点为黑色，就把染黑的任务分配给它的左右儿子，分别让它们继续递归地染黑。由于我们假设的是最短链上的点也存在有红点，所以不存在某条链找不到红点去染黑，因为如果这样的话，那条链将会比最短链还要短（由于假设已经染成了红黑树，所以最短链与这条链有相同数目的黑点，而最短链上还有红点，该链没有，说明该链比最短链还要短）。经过上述调整过程，我们让这棵树的黑需增大了1，也即让最短链上的黑点又多了一个。不断调整，最终最短链上的点一定可以变成全为黑点。证毕。
1.3 算法流程
思路与**树链剖分**有些类似，可以称之为`短链剖分`。对于任意一个子树（包括整个树本身，它可以看作是以真正根节点为根的子树），子树的根记为 ，它的最短链记为 ，最短链长度记为 ，黑需记为 。在这个子树中，我们先染它的最短链 ，染法为：根据  的父亲的染色情况（如果  是整颗树的根，我们约定它的父亲的颜色为红色），尽可能的从上到下（指从  到 NIL 的方向，即深度从小到大的方向）先填入红点，直到剩下的点全部填黑色才能满足黑需要求为止。为了后续证明方便，我们把这样的染色分为两个阶段，第一个阶段称为**红阶段**，即尽可能的染红色（其实就是尽可能的红黑相间），第二个阶段称为**黑阶段**，即从此往后的点都染成黑色的。红阶段的终点在最后一个红点处。按照上述方法把最短链染色后，原本的子树被拆分成若干个更小的子树（即那些根的父亲在最短链上的子树），这些子树则递归地进行上述步骤即可。举一个例子：<br />此时最短链用黄色标记起来了，根据**黑需**部分的约定，我们令整棵树的黑需等于最短链长度，即3。换句话说，整棵树的最短链我们必须全部涂黑，因为一旦黑红交替，有一个红点，就无法满足黑需的要求。于是这颗树此时被染成这样：<br /> 此时树被我们“剖分”成一条已经染好的链和两个子树（它们的根在图上被标记为1和2），我们分别对1、2子树进行染色。先考虑1号子树。<br /> 1号子树的最短链也被大括号标记起来，此时1号子树的黑需为2（因为1号子树的父亲是黑点），所以1号子树的最短链也只能全部染黑。染黑后1号子树还剩下一个更小的子树，用类似的方法可以得到如下结果：<br /> 对于2号子树也类似，最终得到：<br /> 关于这个算法的正确性我们不加以说明，因为这不是问题的关键，这个算法只是为了给下面的理论提供构造上的证明。
二、给出一个判断的理论
**定理**： 如果一棵二叉树上每个点都满足：**以其为根的子树的最长链长度不大于最短链长度二倍，**那么它就可以被染成红黑树，否则就不行。换言之，能否染成红黑树与这一条件是充要关系。证明： 首先我们证明充分性。考虑构造法，我们证明对于每一种符合上述条件（**以其为根的子树的最长链长度不大于最短链长度二倍**）的二叉树都可以构造出一种合法的染色方案。具体的构造方法其实就是我们前文介绍的算法。在这里我们需要证明对于符合条件的二叉树都能通过这个算法构造出合法方案。我们考虑证明：对于一颗树（可能是子树），当我们对它的最短链  成功染色后，一定能对它剖分后形成的  个子树（即那些根的父亲在最短链上的子树）的最短链 成功染色。对于任一剖分后形成的子树的最短链 ，如果它的长度  不小于它的黑需且不大于它的黑需的二倍就一定可以被成功染色，这是非常显然的。如果长度小于黑需，那么全涂黑也不够；如果长度大于黑需二倍，那么就算不断黑红交替黑点也会太多。所以我们转而证明  不会大于它的黑需二倍也不会小于黑需。因为我们假设了原本的树  的最短链  成功染色，而  是原本的树中最短的，又因为  成功染色了，所以子树的最短链 不会因为长度太短而不能按照算法流程染色。证明  不会大于它的黑需二倍比较复杂。首先我们先回忆之前对算法流程中红阶段与黑阶段的定义。我们把一条链的染色分为两个阶段，第一个阶段称为**红阶段**，即尽可能的染红色（其实就是尽可能的红黑相间），第二个阶段称为**黑阶段**，即从此往后的点都染成黑色的。红阶段的终点在最后一个红点处。我们称最短链  所在的子树为 。由于  是被剖分下来的，所以它的根的父亲  应该是  上的一个点。如果  在  上的黑阶段，那么结论立得，因为  往下的点都是黑色的，不妨设有  个，由于我们是对满足条件**以其为根的子树的最长链长度不大于最短链长度二倍**的树进行染色，所以  的长度不会大于 ，而  实际上就是  的黑需，所以  不会大于它的黑需二倍得证。如果  在  上的红阶段，那么我们可以把  与  上  点以上的部分拼在一起考虑，称为 。由于  在  上的红阶段，所以  的长度不大于  的黑需的二倍与  的长度不大于  的黑需的二倍等价。换言之，如果  因为长度太长而无法正常染色，那么  也会因为太长而无法染色；如果  可以正常染色，那么  也可以正常染色。于是问题被相似地转移到了更大的树上，如果更大的树的父亲所在的点处于它所在的最短链的黑阶段，则问题解决；如果它在红阶段，则我们继续把问题转移到更更大的树上。由于整棵树的最短链是全部染黑的，所以每个点都在黑阶段，所以这样的转移一定有结束的时候（最晚就是转移到整棵树的时候）。所以  不会大于它的黑需二倍得证。综上，  不会大于它的黑需二倍也不会小于黑需得证，继而说明对于一颗树（可能是子树），当我们对它的最短链  成功染色后，一定能对它剖分后形成的  个子树（即那些根的父亲在最短链上的子树）的最短链 成功染色。由于对于整棵树的最短链的染色是显然可以成功的，所以我们不断进行剖分就可以对整棵树进行成功染色。故而对于每一种符合条件的二叉树我们都构造出了一种合法的染色方案。充分性得证。必要性是显然的。如果存在一个点使得**以其为根的子树的最长链长度大于最短链长度二倍**，那么无论如何这个子树是无法合法染色的，因为最短链全部染黑，黑点数量也没有最长链多（黑点至少有长度一半）。综上，我们证明了：如果一棵二叉树上每个点都满足：**以其为根的子树的最长链长度不大于最短链长度二倍，**那么它就可以被染成红黑树，否则就不行。换言之，能否染成红黑树与这一条件是充要关系。证毕。
利用这个性质就可以dfs一遍，在线性时间内判断一棵树能否被合法染色。PTA上的题已经AC辽~
完结撒花~
若有收获，就点个赞吧
0 人点赞
