树上只有叶子上的值

Question

几年前,在C#课程中,我学会了编写一个看起来或多或少像这样的二叉树:

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

我看到了它的好处,它在分支上有它的值,这允许快速和容易地查找和插入值,因为它会在每个分支的根上遇到一个值,直到它击中叶子,没有价值.

然而,自从我开始学习Haskell之后; 我见过许多像这样定义的树的例子:

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

这个定义让我很困惑.我看不到在没有分支的元素上使用数据的有用性,因为它最终会导致一个如下所示的树:

对我来说,这似乎是一个设计不佳的List的替代品.它也让我质疑它的查找时间,因为它无法评估哪个分支向下找到它正在寻找的值; 而是需要通过每个节点来找到它正在寻找的东西.

那么,任何人都可以解释为什么第二个版本(叶子上的值)在Haskell中比第一个版本更普遍吗？

Answer 1

我认为这取决于您尝试建模的内容以及尝试建模的方式。

内部节点存储值而叶子只是叶子的树本质上是一个标准的二叉树（树每个叶子NULL都是命令式风格的二叉树）。如果值按排序顺序存储，您现在就有了一个二叉搜索树。以这种方式存储数据有许多特定的优势，其中大部分是直接从命令式设置传输过来的。

叶子存储数据而内部节点仅用于结构的树确实有其优点。例如，红/黑树支持两种强大的操作，称为split并且join在某些情况下具有优势。split将一个键作为输入，然后破坏性地修改树以产生两棵树，其中一棵包含小于指定输入键的所有键，另一棵包含剩余的键。join从某种意义上说，是相反的：它接收两棵树，其中一棵树的值都小于另一棵树的值，然后将它们融合成一棵树。这些操作在大多数红/黑树上特别难以实现，但如果所有数据仅存储在叶子中而不是内部节点中，则要简单得多。这篇详细介绍了红/黑树的命令式实现的论文提到，出于这个原因，一些较旧的红/黑树实现使用了这种方法。

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

concat first second = Branch first second

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

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

希望这可以帮助！

Answer 2

您将叶子上带有数据的树描述为“一个设计不佳的列表替代品”。

我同意这可以用作列表的替代品，但它不一定设计得很差！考虑数据类型

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

您可以定义cons和snoc（附加到列表末尾）操作 -

cons :: t -> Tree t -> Tree t
cons t (Leaf s)     = Branch (Leaf t) (Leaf s)
cons t (Branch l r) = Branch (cons t l) r

snoc :: Tree t -> t -> Tree t
snoc (Leaf s)     t = Branch (Leaf s) (Leaf t)
snoc (Branch l r) t = Branch l (snoc r t)

这些在 O(log n) 时间内运行（对于大致平衡的列表），其中 n 是列表的长度。这与具有 O(1)cons和 O(n)snoc操作的标准链表形成对比。您还可以定义一个常量时间append（如 templatetypedef 的答案）

append :: Tree t -> Tree t -> Tree t
append l r = Branch l r

对于任意大小的两个列表，这是 O(1)，而标准列表是 O(n)，其中 n 是左参数的长度。

在实践中，您可能希望定义这些函数的稍微智能的版本，以尝试保持树的平衡。为此，在分支上提供一些附加信息通常很有用，这可以通过具有多种分支来完成（例如在具有“红色”和“黑色”节点的红黑树中）或明确包含附加数据在分支机构，如

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

例如，您可以size通过在节点的两个子树中存储元素总数来支持 O(1)操作。你对树的所有操作都变得稍微复杂一些，因为你需要正确地保存关于子树大小的信息——实际上，计算树大小的工作在构造树的所有操作上分摊（并巧妙地持久化，以便在以后需要重建大小时完成最少的工作）。