三色二叉树报告.doc

POI VI Stage 3 Problem 1 《三色二叉树》 题意分析 这是一道建立在二叉树模型上的问题。 题目的大意是：要求用红、绿、蓝三种颜色给二叉树的所有节点染色，求绿色点最多（或最少）有多少个，但同时需满足一个约束条件：任意一个节点与其子节点的颜色不同，子节点之间的颜色也需不同。 很显然，“二叉树”是整个问题的建立基础，上述的约束条件则是问题的关键！因此，我们将约束条件置于二叉树模型上分析：尝试在二叉树上染色，在染色同时，注意研究由于约束条件的存在而产生的性质。 举个简单的例子，如图一所示： 显然，上述的三个限制表示的是标号为1、2、3三个点之间的互相关系。除此以外，左子树中的点与右子树中的点没有任何直接的限制关系！ 也就是说，如果我们事先确定了上述二叉树中标号为1、2、3的三个点的颜色，那么接下来，对左子树染色和对右子树染色将变成两个互不干扰的子问题，左子树最值与右子树最值不影响，可以分开求解。 “互不干扰，可以分开求解” ！ 我们需要的正是这句话，如此一来，通过将三点染色，我们就可以把二叉树分成左右两个子树，整个问题被分解成两个较小规模的子问题——我们解题的思路豁然开朗：用“分治法” ！ 下面，我们将应用“分而治之”的思想来设计解决问题的方法。 算法设计 在题意分析中，我们已经明确了用“分治”的思想来设计算法。如图二所示，将二叉树划分成三部分，给标号为1、2、3三个点先染色后，将依次处理左子树，右子树。 在处理时，我们应当注意以下两个问题： 染色的任意性 标号为1、2、3的三个点的颜色并不一定固定依次是红、绿、蓝。我们需要对所有染色情况进行枚举，并对每个染色情况进行左、右子树的分别处理。同样，当根节点只有一个子节点时，我们也要枚举此时的染色方案。 根节点的颜色已确定 由于2号点已经染色，所以，在递归处理左子树时，问题就转化成“根节点颜色已确定，求满足约束条件的最多（最小）染色方案”。 这个转化后的子问题与原问题略有差异：原问题中根节点可以任意染色，而转化后的子问题中根节点的颜色是固定的。 为了便于递归调用相同的处理操作，我们必须保证所有问题的条件与求解目标的统一！于是，有必要将原问题稍做修改：事先求出整个二叉树根节点为红色、绿色或蓝色情况下问题的解（这就与子问题是同一类型了），然后取这三个解中的最大（或最小）值，即得到原问题的解。 分析至此，我们已经得出了解决问题的大致方法： 将原问题转化成“根节点颜色确定，求染色最值方案”； 枚举根节点的左节点与右节点（如果存在）的颜色，同时满足约束条件； 对每种染色方案，递归处理求左、右两子树。 这种方法用递归（有哪些信誉好的足球投注网站）实现起来非常容易，但是效率却不容乐观。是什么导致我们的算法效率低下呢？来看图三： 显然，图三所表示的是两种不同的染色方案。按照我们先前设计的算法，对每种染色方案，都要递归处理左、右两子树。 然而在图三中，两种染色方案的2号节点都是绿色，也就是说，我们将要对“2号节点为绿色”的左子树进行两次相同的递归求解。 这说明算法中存在着重复！如果我们能够避免重复，算法的效率将大大提高。下面，尝试用数学语言对算法重新描述，看看能否找出避免重复的办法。 给二叉树上所有节点标号，从1~N； 用son记录二叉树的构造关系： Son(i,0)和Son(i,1)分别表示编号是i的节点，其左右两个子节点的编号（如果不存在，则用-1表示）。例如在图三中，我们有Son(1,0)=2，Son(1,1)=3。 用F(i,j)表示一个子问题 一个子问题可以由两个参数来描述：根节点编号i，根节点颜色j。 F(i , j)表示：以编号是i、颜色是j的节点为根节点的子树，在满足约束条件的情况下染色，绿色节点最多（最少）有多少个。 按照先前所设计的算法，可以大致得出如下式子： 根据我们的分析，算法会有重复操作，多次计算F(i,j)的值。那么，我们不妨造一个表将F(i,j)保存起来，这样就能有效避免重复计算了——这种方法我们通常称之为“记忆化算法”。 在题目给的条件中，节点数最多有10000个，颜色有三种，所以F(i,j)需要保存的也仅有30000个数值，空间上没有任何问题。消除重复操作后，算法的时间复杂度也仅有O(N)，问题圆满解决了。 在例子以及以后的分析中，我们一直考察的是根节点有左、右两子节点的情况。这种情况更具有普遍意义，经过分析得到的算法也自然可以处理一节点只有一个子节点的情况。 下面的公式是求绿色点最多，而求绿色点最少的式子基本不变，只要将maxof改成minof即可。 2 假设1号点为红色，2号点为绿色，3号点颜色为蓝色。 3 2 1 1号点为二叉树根节点 2号点为左子树根节点 3号点为右子树根节点 3 将整个二叉树划分成三个部分：根节点、左子树、右子树。 由于有约束条件，所以这三个