什么自平衡树在函数式编程中最简单? [英] What Self Balancing Tree is simplest in Functional Programming?

查看:129
本文介绍了什么自平衡树在函数式编程中最简单?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在设计一个Haskell中的自平衡树。作为一个练习,因为它非常适合你的后背。



以前在C和Python中,我倾向于使用Treaps和Splay Trees,因为它们有简单的平衡规则。我总是不喜欢R / B Trees,因为他们看起来工作量比他们的价值还要高。

现在,由于Haskell的功能性质,事情似乎已经发生了变化。我可以在10行代码中编写一个R / B插入函数。另一方面,Treaps需要包装来存储随机数字生成器,而Splay Trees是一种自上而下的痛苦。所以我问你是否有经验与其他类型的树木?
哪些函数更好地利用函数式语言的模式匹配和自顶向下的性质?

解决方案

好吧,我猜想没有太多的参考或研究来回答这个问题。相反,我花时间尝试了不同的想法和树木。我没有发现任何比RB树更好的东西,但也许这只是搜索的偏见。



RB树可以用四个简单的规则来平衡(插入): Chris Okasaki 所示:

  balance T(TR(TR axb)yc)zd = TR(TB axb)y(TB czd)
balance T(TR ax(TR byc )TR(TB axb)y(TB czd)
balance T ax(TR(t) TR byc)zd)= TR(TB axb)y(TB czd)
balance T axb = TB axb

AVL树可以以相似的模式匹配方式进行平衡。然而,规则也不会压缩:

pre $ code> balance T(T axb dx)yc(-1)zd (-2)= T(T axb dx)y(T czd 0)0
balance T ax(T by(T czd dz)1)2 = T(T axb 0)y(T czd dz)0
balance T(T ax(T byc 1)1)zd(-2)= T(T axb -1)y(T czd 0)0
balance T(T ax(T byc( - 1))1)zd(-2)= T(T axb 0)y(T czd 1)0
balance T(T ax(T byc _)1)zd(-2)= T(T axb 0)y(T czd 0)0
balance T ax(T(T byc 1)zd(-1))2 = T(T axb -1)y(T czd 0)0
balance T(T(T byc(-1))zd(-1))2 = T(T axb 0)y(T czd 1)0
balance T ax(T(T byc _)zd 1))2 = T(T axb 0)y(T czd 0)0
余额t = t

由于AVL树的接缝一般被认为不如RB树,所以它们可能不值得额外麻烦。

AA树理论上可以平衡好,轻松通过:

  balance T n(T naxb)yc = T nax(T nbyc) -  skew 
balance T nax(T nby(T nczd))= T(n + 1)(T naxb)y(T nczd) - 分割
余额T naxb = T naxb

但不幸的是,Haskell不喜欢重载 n 。有可能一个较不标准的AA树实现,不是使用等级,而是更类似于R和B的东西,可能会很好。

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



在功能环境中,陷阱也很不容易做,因为您没有全局随机生成器,但需要在每个节点中保留实例。这可以通过将优先级生成任务留给客户来解决,但即使如此,您也无法使用模式匹配进行优先级比较。


I'm designing a self balancing tree in Haskell. As an exercise and because it is nice to have in your back hand.

Previously in C and Python I preferred Treaps and Splay Trees due to their simple balancing rules. I always disliked R/B Trees, since they seemed like more work than they were worth.

Now, due to the functional nature of Haskell, things seem to have changed. I can write a R/B insert function in 10 lines of code. Treaps on the other hand requires wrapping to store the random number generator, and Splay Trees are a pain to do top-down.

So I'm asking if you have experience with other types of trees? Which ones are better at utilizing the pattern matching and top-down nature of functional languages?

解决方案

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.

这篇关于什么自平衡树在函数式编程中最简单?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆