1

虽然我仍在努力寻找解决方案问题,我有另一个可能更容易。下面是冈崎红黑树实现的插入函数。我想要做的是在我插入树时保持数据未排序。因此,每次插入时,数据总是会转到最左边/最底部的叶子。无需比较 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)
4

1 回答 1

1

你可以在haskellDB中使用我的RBTree实现, http: //hackage.haskell.org/package/RBTree

使用insert功能:

insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a

给它一个(\_ _ -> LT)函数,然后你总是可以把新元素放在最左边的地方。

于 2011-06-05T15:10:17.620 回答