我正在Haskell中设计一个自平衡树。作为一项练习，因为能很好地握在您的背上。
以前在C和Python中，由于它们的简单平衡规则，我更喜欢Treaps和Splay Trees。我总是不喜欢R / B树，因为它们看起来比其价值还多。
现在，由于Haskell的功能性质，情况似乎已经改变。我可以用10行代码编写一个R / B插入函数。另一方面，挖掘需要包装以存储随机数生成器，而Splay树很难做到自上而下。
所以我问您是否有其他类型树木的经验？
哪种方法最适合利用功能语言的模式匹配和自上而下的特性？
最佳答案
好的，我想没有很多参考或研究可以回答这个问题。取而代之的是，我花时间尝试您的不同想法和想法。我没有找到比RB树更好的东西，但是也许这只是搜索偏见。
RB树可以(插入)与四个简单规则(如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树可以以类似的模式匹配方式进行平衡。但是，规则也不会压缩:
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)可能会很好地工作。展开树很困难，因为您需要专注于单个节点，而不是树的静态结构。可以通过merging insert and splay完成。
在功能环境中执行陷阱也不容易，因为您没有全局随机数生成器，但需要在每个节点中保留实例。 leaving the task of generating priorities to the client可以解决这个问题，但是即使如此，您也无法使用模式匹配来进行优先级比较。