什么自平衡树在函数式编程中最简单?

好吧,我想回答这个问题的参考文献和研究不多。相反,我花时间去尝试你不同的想法和方法。我没有发现比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 . 不使用秩,而使用更类似于R和B的方法来实现a a树,可能会工作得更好。

Splay树很困难,因为您需要关注单个节点,而不是树的静态结构。它可以通过 merging insert and splay .

treap在功能环境中也很难实现,因为您没有全局随机生成器,但需要在每个节点中都保留实例。这可以通过 leaving the task of generating priorities to the client ,但即使这样,也不能使用模式匹配进行优先级比较。

正如你所说,红黑树并不难用。你给过吗 finger trees a look ? 您可能对使用类似于 zipper. 你可能会发现另一棵有趣的树是 AA tree 它是红黑树的简化。

这是一个已经实现的。

Haskell中有平衡树的良好实现,如Data.Map和Data.Set。他们不满足你的需要吗?不要重新实现,重复使用。

OCaml标准库使用AVL树 map 函子。如果包含 remove 操作。