我正在 Haskell 中设计一个自平衡树。作为一项练习，因为它很好地放在你的后手上。
以前在 C 和 Python 中，我更喜欢 Treaps 和 Splay Trees，因为它们的平衡规则很简单。我一直不喜欢 R/B 树，因为它们看起来比它们的价值更多。
现在，由于 Haskell 的功能特性，事情似乎发生了变化。我可以用 10 行代码编写一个 R/B 插入函数。另一方面，Treaps 需要包装来存储随机数生成器，而 Splay Trees 自顶向下做起来很痛苦。
所以我问你是否有其他类型的树木的经验？哪些更擅长利用函数式语言的模式匹配和自上而下的特性？
好的，我想没有很多参考资料或研究可以回答这个问题。相反，我花时间尝试了您的不同想法和树。我没有发现比 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. 不使用等级但更类似于 R 和 B 的 AA 树的不太标准的实现可能会很好地工作。
展开树很困难，因为您需要关注单个节点，而不是树的静态结构。它可以通过合并 insert 和 splay来完成。
Treap 在功能环境中也不容易做到，因为您没有全局随机生成器，但需要在每个节点中保留实例。这可以通过将生成优先级的任务留给客户端来解决，但即便如此，您也无法使用模式匹配进行优先级比较。
正如您所说，红黑树并不难使用。你看过手指树吗？您可能有兴趣使用诸如拉链之类的东西来扩充您的基础数据结构。 您可能会发现有趣的另一棵树是AA 树，它是红黑树的简化版。
这是已经实施的。
Haskell 中有很好的平衡树实现，例如 Data.Map 和 Data.Set。他们不能满足你的需求吗？不要重新实现，重用。
OCaml 标准库使用 AVL 树作为其map函子。如果包含操作，似乎它比 RB-tree 更容易实现remove。