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

发布于 2024-10-02 01:56:35 字数 314 浏览 9 评论 0原文

我正在 Haskell 中设计一棵自平衡树。作为一种练习，因为握在后手上感觉很好。

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

现在，由于 Haskell 的函数性质，事情似乎发生了变化。我可以用 10 行代码编写一个 R/B 插入函数。另一方面，Treaps 需要包装来存储随机数生成器，而 Splay Trees 则很难从上到下进行。

所以我想问你是否有种植其他类型树木的经验？哪些更擅长利用函数式语言的模式匹配和自上而下的性质？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

谁许谁一生繁华 2024-10-09 01:56:35

好吧，我想没有太多参考资料或研究来回答这个问题。相反，我花时间尝试了你们不同的想法和树木。我没有找到比 RB 树更好的东西，但这也许只是搜索偏差。

RB 树可以通过四个简单规则进行（插入）平衡，如所示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 树通常被认为不如 RB 树，因此它们可能不值得额外的麻烦。

理论上，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 的重载。 AA 树的不太标准的实现（不使用等级，而是使用更类似于 R 和 B 的东西）可能会很好地工作。

展开树很困难，因为您需要关注单个节点，而不是树的静态结构。可以通过合并插入和展开来完成。

在功能环境中也很难进行 Treap，因为您没有全局随机生成器，但需要在每个节点中保留实例。这可以通过将生成优先级的任务留给客户端，但即便如此，您也无法使用模式匹配进行优先级比较。

Ok, I guess there wasn't a lot of references or research for answering this question. Instead I've taken the time to try your different ideas and trees. I didn't find anything a lot better than RB trees, but perhaps that's just search bias.

The RB tree can be (insertion) balanced with four simple rules, as shown by 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 trees can be balanced in a similar pattern matching way. However the rules don't compress as well:

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

As AVL trees seams to generally be considered inferior to RB trees, they are probably not worth the extra hassle.

AA trees could theoretically be balanced nice and easily by:

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

But unfortunately Haskell don't like the overloading of n. It is possible that a less standard implementation of AA trees, not using ranks, but something more similar to R and B, would work well.

Splay trees are difficult because you need to focus on a single node, rather than the static structure of the tree. It can be done by merging insert and splay.

Treaps are also uneasy to do in a functional environment, as you don't have a global random generator, but need to keep instances in every node. This can be tackled by leaving the task of generating priorities to the client, but even then, you can't do priority comparison using pattern matching.

回复收藏 0 原文