6

有时我让自己在 Haskell 中使用不同类型的树，但我不知道它们被称为什么，也不知道从哪里获得有关使用它们的算法或它们的类实例的更多信息，甚至不知道一些关于 hackage 的预先存在的代码或库。

例子：

标签在叶子或树枝上的二叉树：

data BinTree1 a = Leaf | 
                  Branch {label :: a, leftChild :: BinTree1 a, rightChild :: BinTree1 a}

data BinTree2 a = Leaf {label :: a} | 
                  Branch {leftChild :: BinTree2 a, rightChild :: BinTree2 a}

类似地，带有每个子节点标签的树或所有子节点的通用标签：

data Tree1 a = Branch {label :: a, children :: [Tree1 a]}

data Tree2 a = Branch {labelledChildren :: [(a, Tree2 a)]}

有时我开始使用Tree2，并且在开发过程中不知何故被重构为Tree1，这似乎更容易处理，但我从来没有考虑过很多。这里有某种二元性吗？

另外，如果您可以发布一些您认为有用的其他不同种类的树，请发布。

总而言之：你能告诉我的关于这些树的一切都会很有用！:)

谢谢。

编辑：

澄清：这不是家庭作业。只是我通常最终会使用这些数据类型并创建实例（Functor、Monad 等），也许如果我重新命名它们的名称，我会找到包含已实现的东西和更多理论信息的库。

通常，当 Hackage 上的库名称中有 Tree 时，它​​会实现 BinTree2 或仅在叶子上带有标签的非二叉树的某些版本，所以在我看来，Tree2 和 BinTree2 可能有其他名称或标识符。

另外我觉得可能存在某种对偶性或同构，或者一种将使用 Tree1 的代码转换为使用 Tree2 并进行一些转换的代码的方法。在那儿？可能只是印象。

4

2 回答 2

6

我听过的名字：

  • BinTree1是二叉树
  • BinTree2不知道名称，但您可以使用这样的树来表示无前缀代码，例如霍夫曼编码
  • Tree1是一棵玫瑰树
  • Tree2[Tree1]与（的森林）等距Tree1或以其他方式查看它是Tree1没有根标签的。
于 2012-08-19T23:08:25.467 回答
5

BinTree2仅在叶子（

因此，如果您有 4 个具有以下哈希码的值：

...000001 A
...000010 B
...000011 C
...000010 D

...您可以将它们存储在二叉树（隐式帕特里夏树）中，如下所示：

     +          <- Bit #1 (least significant bit) of hash code
    / \            0 = left, 1 = right
   /   \
[B, D]  +       <- Bit #2
       / \
      /   \
     [A]  [C]

我们看到，由于B和D“开始”的哈希码是0，它们存储在左根孩子中。它们具有完全相同的哈希码，因此不再需要分叉。A和的哈希码C都以 1 “开始”，因此需要另一个分叉。A位 2 as 0，所以它向左，而 C with1向右。

这种哈希表实现有点糟糕，因为当插入某些元素时可能必须重新计算哈希值，但没关系。

BinTree1只是一个普通的二叉树，用于快速基于顺序的集合。没什么好说的了，真的。

Tree1和之间的唯一区别Tree2是Tree2不能有根节点标签。这意味着如果用作前缀树，它不能包含空字符串。它的用途非常有限，我在实践中还没有看到类似的东西。Tree1但是，正如我所说，显然可以用作非二进制前缀树。

于 2012-08-19T22:20:20.687 回答