只有叶子节点有值的树

Question

只有叶子节点有值的树

15

几年前，在一门C#课程中，我学会了编写一个二叉树，看起来差不多是这样的：

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

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

每个带数字的圆圈是一个分支

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

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

这个定义让我感到困惑。我看不出记录那些不分支的元素数据有什么用处，因为这最终会导致一棵树看起来像这样：

The circles with numbers are Leaf nodes

对我来说，这似乎是一个设计不良的列表替代品。这也让我质疑它的查找时间，因为它无法评估应该走哪个分支以找到它正在寻找的值；而是需要遍历每个节点才能找到它要查找的内容。

那么，有人能解释一下为什么在Haskell中第二个版本（将值放在叶子节点上）比第一个版本更常见吗？

- Electric Coffee

当然你可以在C#中做到这一点，而且如果你知道怎么做的话，这也相当容易。 - Electric Coffee

2

它们只是两种不同的数据结构，可能有不同的用途、优点和缺点（也可能没有）。例如，Data.IntMap 是后一种形式（仅在叶子节点上有数据），而 Data.Map 是前一种形式。为什么要同时拥有这两个呢？文档中这样说：“[IntMap] 在联合和交集等二进制操作上表现特别好。然而，我的基准测试显示，与 [Data.Map] 相比，在插入和删除时它也（更）快。”最后，我不会说第二个版本“更为普遍”。 - user2407038

3个回答

5

你描述了一棵带有叶子节点数据的树，称其为“不好的列表替代品”。

我认为这可以作为列表的替代品，但不一定设计得不好！请考虑数据类型。

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)

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

- Chris Taylor

这种列表添加分支确实更容易，但如果这些分支本身不包含任何数据，我就看不出有什么好处了。为什么要添加更多没有数据的分支呢？这不是只会不必要地增加树的大小吗？ - Electric Coffee

1

请注意，这种数据类型包括（非空）链表作为其子集，因为您可以将所有左侧分支设置为Leaf a。因此，这种数据结构能够执行常规链表所能执行的任何操作（而且还具有快速访问最后一个元素、快速snoc、快速append等功能）。非空列表是data List a = Leaf a | Branch a (List a) - 你会说这个在分支上有数据吗？如果是这样的话，那么从某种意义上说，叶子节点上有数据的树也在分支上有数据（只是数据以另一棵树的形式存在）。 - Chris Taylor

1

更多不一定代表更好，我将解释一些基本的考虑因素来说明为什么你的直觉是错误的。然而，总体思路是不同的数据结构需要不同的东西。

在某些情况下，空叶节点实际上可能会成为一个空间（因此时间）问题。如果一个节点由一位信息和两个指向其子节点的指针表示，那么对于每个子节点都是叶子节点的节点，您将得到两个空指针。这是每个叶节点的两个机器字，这可能会占用相当大的空间。一些结构通过确保每个叶子至少持有一个信息以证明其存在来避免这种情况。在某些情况下（例如ropes），每个叶子可能具有相当大且密集的有效负载。

使内部节点变大（通过在其中存储信息）会使修改树的成本更高。在平衡树中更改叶子通常会强制您为O(log n)个内部节点分配替换。如果每个节点都更大，那么您刚刚分配了更多的空间并花费了额外的时间来复制更多的单词。内部节点的额外大小还意味着您可以将更少的树结构放入CPU缓存中。

- dfeuer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

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

内部节点存储值，而叶子节点只是叶子的树本质上是标准的二叉树（将每个叶子视为NULL，基本上就有了命令式样式的二叉树）。如果按排序顺序存储值，则现在具有二叉搜索树。以这种方式存储数据有许多特定的优点，其中大多数直接从命令式设置中转移。

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

作为将键存储在叶子中的另一个潜在优点，请假设您想要实现连接操作，该操作将两个列表合并在一起。如果没有数据在叶子中，那么这就像

concat first second = Branch first second

这是因为这些节点中没有存储任何数据。如果数据存储在叶子节点中，则需要将一个键从其中一个叶子节点移动到新的连接节点，这需要更多的时间并且更加棘手。

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

希望这可以帮助您！