logo标签列表

在函数式编程中，哪种自平衡树最简单？

haskellfunctional-programmingtreetree-balancing
19

我正在使用Haskell设计一棵自平衡树。这是一个练习，也因为拥有这种技能非常好。

以前在C和Python中，我更喜欢Treaps和Splay Trees，因为它们具有简单的平衡规则。我一直不喜欢R/B Trees，因为它们似乎比他们价值得多的工作。

现在，由于Haskell的函数式特性，情况似乎发生了变化。我可以用10行代码编写R/B插入函数。而Treaps需要包装来存储随机数生成器，而自上而下地进行Splay Trees则相当麻烦。

因此，我想问你是否有其他类型的树的经验？ 哪些树更擅长利用函数式语言的模式匹配和自上而下的特性？

6
不是直接的答案，但建议阅读《纯函数数据结构》以获取一些好的想法。 - Jeff Foster
我喜欢它。它没有过多涉及详细结构，但提供了一个很好的总体观点。 - Thomas Ahle
你需要一个搜索树，还是一个序列的树形表示（例如指尖树 - 具有连接和分割功能）？在后一种情况下，纯函数2-3树是微不足道的。 - jkff
4个回答
8
好的，我猜回答这个问题并没有很多参考资料或研究。相反，我花时间尝试了您提出的不同想法和树。我没有找到比红黑树更好的东西，但也许这只是搜索偏见。
红黑树可以通过四条简单的规则（如Chris Okasaki所示）进行（插入）平衡。
balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance T a x b = T B a x b

AVL树可以通过类似模式匹配的方式实现平衡。然而，规则不会像之前那样压缩得那么好：

balance T (T (T a x b   dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d  0) 0
balance T a x (T b y (T c z d   dz)   1 )   2  = T (T a x b  0) y (T c z d dz) 0
balance T (T a x (T b y c   1 )   1 ) z d (-2) = T (T a x b -1) y (T c z d  0) 0
balance T (T a x (T b y c (-1))   1 ) z d (-2) = T (T a x b  0) y (T c z d  1) 0
balance T (T a x (T b y c   _ )   1 ) z d (-2) = T (T a x b  0) y (T c z d  0) 0
balance T a x (T (T b y c   1 ) z d (-1))   2  = T (T a x b -1) y (T c z d  0) 0
balance T a x (T (T b y c (-1)) z d (-1))   2  = T (T a x b  0) y (T c z d  1) 0
balance T a x (T (T b y c   _ ) z d (-1))   2  = T (T a x b  0) y (T c z d  0) 0
balance t = t

作为AVL树似乎普遍被认为不如红黑树，它们可能不值得额外的麻烦。
AA树理论上可以通过以下方式很好地平衡：
balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b

但不幸的是，Haskell 不喜欢 n 的重载。可能一个使用类似 R 和 B 的更少标准化实现 AA 树会很好。

Splay 树很困难，因为你需要专注于单个节点，而不是树的静态结构。可以通过 合并插入和 splay 来完成。

在函数环境中，Treap 也很难做到，因为你没有全局的随机生成器，但需要在每个节点中保留实例。这可以通过 将生成优先级的任务留给客户端 来解决，但即使这样，你也不能使用模式匹配进行优先级比较。

6
正如你所说，红黑树并不难使用。你有没有看过 finger trees？ 你可能会有兴趣用类似于zipper的东西来增强你的基础数据结构。另一个你可能会感兴趣的树是AA tree，它是红黑树的简化版本。
指针树看起来非常酷。我很高兴你让我发现了这种数据结构。然而，它们似乎不是特别容易实现。我见过的大多数实现都使用2-3树，并将树推广到许多用例。 - Thomas Ahle
1
你可能会对AA树感兴趣，它们只是简化的红黑树。 - stonemetal
谢谢你向我介绍AA树，我很喜欢它们！不幸的是，它们使用的排名与模式匹配不太兼容 :( - Thomas Ahle
4

这已经是一个已经实现的方案。

Haskell中有一些良好的平衡树实现，例如Data.Map和Data.Set。它们是否满足您的需求？不要重新实现，重复使用。

4
为了算法目的，通常需要一棵树来存储每个节点中的特定信息，例如统计树中子树的大小或区间树中最右侧点的位置。请注意，翻译过程中不能改变原文意思，也不要加入任何解释性内容。 - Thomas Ahle
1

OCaml标准库使用AVL树作为其map函数对象。如果包括remove操作，似乎比实现RB树更容易。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接