如何高效枚举满足等价关系的指定大小唯一黑白二叉树？

核心思路：基于规范形式的递归生成 #

直接生成每个等价类的唯一规范表示，从根源避免等价树的产生，无需事后去重。关键是利用给定的等价关系定义规范形式的约束，在递归生成过程中严格遵循约束。

1. 定义规范形式的约束 #

根据等价关系：

∀ a b c d . Black (White a b) (White c d) == White (Black a c) (Black b d)

我们设定禁止构造Black节点的两个子节点均为White节点的结构。也就是说：

• 若节点为Black，则其左、右子节点不能同时是White节点；
• White节点的子节点可以是任意合法的规范树（包括Black节点）。

该约束确保每个等价类仅对应一个规范树：所有符合等价关系左侧的结构都会被转换为右侧的White节点形式，而右侧结构不会触发进一步的归约，是最终的规范形态。

2. 递归生成规范树 #

按树的大小（构造函数数量）n递归生成所有规范树：

• 基础情况：当n=1时，所有树为Leaf k（k为指定范围内的Nat值，若未限定范围则需根据需求调整）。
• 递归情况：对于n>1，树分为两种类型，且需满足size(t1) + size(t2) = n-1（当前节点占1个构造函数）：
  • 生成White t1 t2：枚举所有满足大小条件的规范树t1和t2的组合，无额外约束；
  • 生成Black t1 t2：枚举所有满足大小条件的规范树t1和t2的组合，但需排除t1和t2均为White节点的情况。

3. 优化策略：缓存子问题结果 #

为避免重复计算，缓存每个大小k对应的所有规范树列表。递归生成时直接复用缓存结果，时间复杂度与最终唯一树的数量成正比，远优于暴力法的平方级复杂度。

示例验证 #

以等价关系中的例子为例：

• 暴力法会生成Black (White 0 1) (White 2 3)，但该结构违反Black节点的约束，不会被我们的算法生成；
• 其等价的规范树White (Black 0 2) (Black 1 3)会被正常生成，且是该等价类的唯一代表。

方法优势 #

• 无冗余生成：通过约束直接跳过所有等价结构，避免资源浪费；
• 低时间复杂度：递归+缓存的方式无需事后与所有已生成树比较，效率显著提升。

内容的提问来源于stack exchange，提问作者MaiaVictor