如何有效地枚举二叉黑白树，同时考虑对称性？

Question

考虑以下类型的黑白二叉树：

\n

data BW = Black BW BW | White BW BW | Leaf Nat\n

\n

具有如下等价关系：

\n

\xe2\x88\x80 a b c d . Black (White a b) (White c d) == White (Black a c) (Black b d)\n

\n

例如，Black (White 0 1) (White 2 3)和White (Black 0 2) (Black 1 3)是等价的。我感兴趣的是尽可能有效地枚举给定大小的所有唯一树（其中树的大小只是构造函数的数量）。暴力方法仅涉及枚举给定深度的所有树，并过滤掉等效的树。由于以下两个原因，这将非常低效：

\n

\n

1. 它将浪费地生成/考虑大量等效树

   \n
\n

2. 过滤将是二次的，因为它需要与所有以前的树进行比较

   \n
\n

\n

是否有一种有效的算法来生成给定深度的所有 BW 树，而不生成相同的树？

\n

Answer 1

给定任何 BW 树，您可以系统地将其转换为不包含具有White两个Black子节点的节点的等效树，从根开始递归工作。

此外，生成的“偏黑”树将与原始树大小相同，并且没有两棵这样的偏黑树将是等效的，除非它们完全相同。

因此，偏黑树可以用作规范形式，并且您可以枚举给定大小的偏黑树：

data BT = Black BBT BBT | BTLeaf Nat
data WT = WhiteWW WT WT | WhiteWB WT BT | WhiteBW BT WT | WTLeaf Nat
data BBT = BT BT | WT WT