自平衡树在功能编程中最简单的是什么？

Question

我正在Haskell中设计一个自平衡树.作为一项练习,因为你的后背很好.

之前在C和Python中,由于其简单的平衡规则,我更喜欢Treaps和Splay Trees.我总是不喜欢R/B树,因为它们似乎比它们的价值更多的工作.

现在,由于Haskell的功能性,事情似乎发生了变化.我可以用10行代码编写一个R/B插入函数.另一方面,Treaps需要包装以存储随机数生成器,并且Splay Trees是自上而下的痛苦.

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

Answer 1

好吧,我想没有很多参考或研究来回答这个问题.相反,我花时间尝试你的不同想法和树木.我没有找到比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,可能会很好.

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

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

Answer 2

正如你所说,红黑树并不难以使用.你看过手指树了吗？您可能有兴趣使用类似拉链的方式扩充基础数据结构. 你可能会觉得有趣的另一棵树是AA树,它是红黑树的简化.