PQ 树


PQ 树是一种基于树的数据结构,代表一组元素上的一系列排列,由 Kellogg S. Booth 和 George S. Lueker 于 1976 年发现命名,用来解决以下问题

给出 个集合 ,你要找到一个 的排列,使得每个集合内的元素都相邻。

PQ 树可以在 时间内构建。本文中介绍的构建方法时间复杂度为

定义

PQ 树有三种结点:叶子结点P 结点Q 结点。其中叶子结点代表排列中的一个元素,P 结点表示它的子结点可以任意排列,Q 结点表示它的儿子顺序可以反转。所有非叶子结点都是 P 结点或 Q 结点中的一种。P 结点至少有 2 个儿子,Q 结点至少有 3 个儿子。
由于结点的定义,PQ 树本身代表了 所有的 合法方案,其先序遍历就是其中之一。
下图是一棵 PQ 树。

其先序遍历 1,2,3,4,5 代表了一个合法方案。如果 P 结点的儿子重排列为 4,2,3,我们得到了另一个合法方案 1,4,2,3,5。保持 P 结点儿子顺序不变,Q 结点的儿子顺序反转,得到了另一个合法方案 5,3,2,4,1。

构建

PQ 树使用儿子 - 兄弟表示法。

我们增量构建一棵 PQ 树。

首先建立一棵树,其根为 P,总共 个儿子,分别是 ,代表没有任何限制时的 PQ 树。随着限制的不断加入,我们不断修改这棵树。

当加入一个新的限制集合 时,我们把所有属于这个集合的叶子结点标记为 黑色,不在这个集合内的叶子结点标记为 白色。对于所有非叶子结点,如果其所有儿子均为黑色,将其也标记为黑色;如果其所有儿子均为白色,将其也标记为白色;否则将其标记为 灰色。在下面的图中,黑色结点、白色结点、灰色结点分别用黑色、灰色、一半黑一半灰来表示。

我们要求 PQ 树中的结点按照颜色排序。

自底向上法

包含所有黑色结点的最小子树被称为 相关子树,相关子树的根(不一定是整棵树的根)被称为 相关根

添加一个限制的过程被称为 reduction。一次 reduction 分为两个阶段:冒泡阶段和减少阶段。

冒泡阶段

冒泡阶段只处理相关子树。我们将相关子树中的所有结点标记为黑色或灰色,并为每个结点计算其拥有的相关子结点数量。为了高效地完成这个过程,我们从叶子往根处理相关子树。这需要记录每个点的父亲结点,但在减少阶段一个点的父亲结点经常要被修改。为了在线性时间内构造,只有 P 结点的儿子和 Q 结点的最后一个儿子 始终记录正确的父亲结点。对于 Q 结点的其他儿子,在冒泡阶段用最后一个儿子的父亲更新他们的父亲。

当遇到一个中间的结点时,我们看一下它的兄弟是否已经有合法的父亲结点。如果没有,将其标记为 阻塞 的。如果后面它的兄弟有了合法的父亲,那么修改这个结点的父亲并且取消标记。如果在冒泡阶段结束时,仍然有一段连续的阻塞结点(如下面的情况 Q3),一个没有父结点的“伪结点”成为该块的父结点,并在减少阶段时被去除。

减少阶段

减少阶段用一个队列来处理结点。首先将所有限制内的叶子结点加入队列。每次取出队首的结点 并处理。如果 的父亲也是相关子树内的结点,那么将 入队。
对于每一个结点 ,我们分情况讨论。如果不属于其中任何一种情况,则无解。

叶子结点

标记为黑色。

P 结点

如果所有儿子均为黑色,将 标记为黑色。

如果 有黑色儿子和白色儿子,且 是相关根,那么新建一个 P 结点 成为它所有黑色儿子的根。

如果 有黑色儿子和白色儿子,且 不是相关根,那么做以下操作:

  • 新建一个 P 结点 成为所有黑色儿子的根。
  • 新建一个 P 结点 成为所有白色儿子的根。
  • 如果 (和/或 )只有一个儿子,那么不要新建结点,而是将 (和/或 )直接赋值成那个儿子。
  • 改成 Q 结点并把其儿子设为 ,将其标记为灰色。

注意到根据之前的定义,Q 结点至少有 3 个儿子,因此这里的 被视为一个”伪结点“,并且将在后面被继续处理。

如果 有一个灰色儿子 ,且 是相关根,那么新建一个 P 结点 作为其所有黑色儿子的根,将 的兄弟设为 最后一个一个黑色儿子,然后把 设为 的最后一个儿子。

如果 有一个灰色儿子 ,且 不是相关根,那么进行以下操作:

  • 新建一个 P 结点 成为所有黑色儿子的根。
  • 新建一个 P 结点 成为所有白色儿子的根。
  • 如果 (和/或 )只有一个儿子,那么不要新建结点,而是将 (和/或 )直接赋值成那个儿子。
  • 的兄弟设为 最后一个白色儿子,然后把 设为 的最后一个儿子。
  • 的兄弟设为 最后一个黑色儿子,然后把 设为 的最后一个儿子。


如果 恰有两个灰色儿子 ,那么进行以下操作:

  • 新建一个 P 结点 成为所有黑色儿子的根。
  • 如果 只有一个儿子,那么不要新建结点,而是将 直接赋值成那个儿子。
  • 的最后一个黑色儿子的兄弟设为
  • 的兄弟设为 的最后一个黑色儿子。
  • 的最后一个儿子设为 的最后一个白色儿子。

可以发现这样 就被合并进了

Q 结点

如果 只有黑色儿子,那么将 标记成黑色。(下面的图的形状错了。)

如果 有一个灰色儿子 ,且所有标记相同的儿子均连续出现,那么进行如下操作:

  • 最后一个黑色儿子, 最后一个白色儿子, 的黑色兄弟, 的白色兄弟。
  • 的兄弟设为 的兄弟设为
  • 如果 没有一个白色兄弟或黑色兄弟,将 的最后一个儿子设成 的最后一个儿子。
  • 删除


如果 恰有两个灰色儿子 ,且所有标记相同的儿子均连续出现,那么对 都进行上一种操作即可。

该构建方法是原论文中的,但是实现较为不便。

自顶向下法

目前 OI 中的实现大多采用该方法。其实方法类似,下面出现的情况基本都能在上面找到。

注意到根据之前的染色过程,所有黑色和白色的点都已经满足条件,因此我们 只需要处理灰色结点

P 结点

  • 如果 有多于两个灰色儿子,无解。
  • 如果 只有一个灰色儿子,且没有黑色儿子,递归处理灰色儿子。
  • 否则先清空 的儿子,然后加入所有的白色儿子。新建一个 Q 结点 并成为 的儿子。在 中加入所有的灰色儿子。新建一个 P 结点 作为所有黑色儿子的根,将 插入 的中间。(对应了自底向上法 P 结点的所有情况。)

注意到我们会要求两个灰色节点白色全在左侧,黑色全在右侧(或相反),因此我们需要实现一个分裂函数 split,可以把这个子树的点分裂成黑白部分,并同时保留分裂成的子树的节点的 所有可能

Q 结点

  • 找到最左边和最右边的非白色节点位置 。如果 内有非黑色节点,无解。
  • 如果没有黑色节点,只有一个灰色节点,递归处理这个灰色节点,否则只需要将 位置的节点分裂。

分裂函数

令要分裂的点为 ,我们想把 分裂成左边全是白色,右边全是黑色的森林。如果 不是灰色结点则直接返回子树。只考虑灰色结点的情况。 如果 是 P 类结点:

  • 如果 有至少两个灰色儿子,则无解。
  • 否则左边是所有白色儿子,中间递归处理灰色儿子,右边是所有黑色儿子。注意到要保留所有的可能,因此要新建两个 P 结点分别作为白色儿子和黑色儿子的根。(对应自底向上法的 P4 情况。)
  • 删除

如果 是 Q 类结点:

  • 如果正序和反序都不满足白 - 灰 - 黑,则无解。
  • 如果有至少两个灰色儿子,也无解。
  • 否则递归分裂灰色儿子即可。
  • 删除

最后把所有多余的结点(只有一个儿子的结点)删除。

代码实现

习题

参考资料

贡献者:@R-G-Mocoratioen@Ir1dXD@xyf007@Danni

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组