虽然我仍在努力寻找解决方案问题,我有另一个可能更容易。下面是冈崎红黑树实现的插入函数。我想要做的是在我插入树时保持数据未排序。因此,每次插入时,数据总是会转到最左边/最底部的叶子。无需比较 x < y、x > y 或 x == y。一开始似乎很简单,只需移除这些防护,然后只做:ins s@(T color ayb) = balance color (ins a) y b。行为似乎是树保持平衡,但颜色变得有点混乱。最终这会影响未来的插入。知道如何实现这一点吗?我认为这可能是我对上一个问题的第一步。我刚开始玩 Haskell,所以我没有把它简单化。非常感谢。
insertSet x s = T B a y b
where ins E = T R E x E
ins s@(T color a y b) =
if x < y then balance color (ins a) y b
else if x > y then balance color a y (ins b)
else s
['d','a','s','f'] s
/\
a f
/
d (unsorted tree)