haskell - 仅在叶子上具有值的树

Question

几年前，在 C# 类(class)中，我学会了编写一个或多或少像这样的二叉树:

data Tree a = Branch a (Tree a) (Tree a) | Leaf

我看到了它的好处，它在分支上有它的值，这允许快速轻松地查找和插入值，因为它会在每个分支的根部一直遇到一个值，直到它遇到一个值。叶子，没有任何值(value)。

然而，自从我开始学习 Haskell 以来；我见过很多这样定义的树的例子:

data Tree a = Branch (Tree a) (Tree a) | Leaf a

这个定义让我困惑。我看不出在不分支的元素上获取数据有什么用处，因为它最终会导致一棵如下所示的树:

对我来说，这似乎是一个设计糟糕的列表替代方案。这也让我质疑它的查找时间，因为它无法评估要向下查找哪个分支来查找它正在查找的值；而是需要遍历每个节点才能找到它要查找的内容。

那么，有人能解释一下为什么第二个版本(叶子上的值)在 Haskell 中比第一个版本更流行吗？

Answer 1

我认为这取决于您想要建模的内容以及如何建模。

内部节点存储值并且叶子只是叶子的树本质上是一个标准的二叉树(树的每个叶子都为NULL，并且基本上有一个命令式的二叉树)。如果值按排序顺序存储，那么您现在就有了一个二叉搜索树。以这种方式存储数据有许多具体的优点，其中大部分直接从命令式设置传输。

叶子存储数据而内部节点仅用于结构的树确实有其优点。例如，红/黑树支持两种强大的操作，称为split和join，它们在某些情况下具有优势。 split 将一个键作为输入，然后破坏性地修改树以生成两棵树，其中一棵包含小于指定输入键的所有键，另一棵包含剩余的键。从某种意义上来说，join 是相反的:它接受两棵树，其中一棵树的值都小于另一棵树的值，然后将它们融合在一起形成一棵树。这些操作在大多数红/黑树上实现起来特别困难，但如果所有数据仅存储在叶子中而不是内部节点中，则要简单得多。 This paper detailing an imperative implementation of red/black trees提到出于这个原因，一些旧的红/黑树实现使用了这种方法。

作为在叶子中存储键的另一个潜在优势，假设您想要实现连接操作，将两个列表连接在一起。如果叶子中没有数据，这很简单

concat first second = Branch first second

这是可行的，因为这些节点中没有存储任何数据。如果数据存储在叶子中，您需要以某种方式将键从其中一个叶子移动到新的串联节点，这需要更多时间并且更难以处理。

最后，在某些情况下，您可能希望将数据存储在叶子中，因为叶子与内部节点根本不同。例如，考虑一棵解析树，其中叶子存储解析中的特定终结符，内部节点存储产生式中的所有非终结符。在这种情况下，确实有两种不同类型的节点，因此在内部节点中存储任意数据是没有意义的。

希望这有帮助!