我一直在研究Haskell中的RB树实现，但是很难对其进行一些更改，因此数据仅放在叶子中，就像在二叉叶子树中一样：

    /+\
   /   \
 /+\    \
/   \    c
a   b

除了节点的颜色外，内部节点还将保存其他信息，例如树的大小（就像在正常的RB树中一样，但数据保留在叶子上）。我也不需要对要插入的数据进行排序。在插入数据时，我仅使用RB来获得平衡的树，但我想保持数据插入的顺序。

原始代码是（来自冈崎的书）：

data Color = R | B
data Tree a = E | T Color (Tree a ) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x s = makeBlack (ins s)
    where ins E = T R E x E
        ins (T color a y b) 
            | x < y = balance color (ins a) y b
            | x == y = T color a y b
            | x > y = balance color a y (ins b)
        makeBlack (T _ a y b) = T B a y b

我将其更改为：（导致异常：函数ins中的非穷举模式）

data Color = R | B deriving Show
data Tree a = E | Leaf a | T Color Int (Tree a) (Tree a)

insert :: Ord a => a -> Set a -> Set a
insert x s = makeBlack (ins s)
    where 
        ins E = T R 1 (Leaf x) E
        ins (T _ 1 a E) = T R 2 (Leaf x) a
        ins (T color y a b)
            | 0 < y = balance color y (ins a) b
            | 0 == y = T color y a b
            | 0 > y = balance color y a (ins b)
        makeBlack (T _ y a b) = T B y a b

原始平衡功能为：

balance B (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 B (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 B 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 B 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 color a x b = T color a x b

从上面的代码可以明显看出，我做了一些更改。

在此先感谢您的帮助:)

编辑：对于我正在寻找的表示形式，克里斯·冈崎（Chris
Okasaki）建议我使用二进制随机访问列表，如他的书中所述。另一种选择是简单地修改Data.Set中的代码，将其实现为权重平衡树。