algorithm - 我可以在红黑树中插入未排序的数据吗？

Question

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

Answer 1

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

使用insert功能：

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

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