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

虽然我还在努力寻找this问题的解决方案，但我还有另一个可能更容易的解决方案。以下是冈崎红黑树实现的插入功能。我想要做的是保持数据未排序，因为我插入到树中。因此，每次插入数据时，数据都会始终显示在最左边/最底部的页面上。没有必要比较x < y，x> y或x == y。看起来非常简单，首先删除这些警卫并且只做：ins s @（T color a y b）=平衡颜色（ins a）y b。行为似乎是树保持平衡，但着色变得有点混乱。最终影响未来插入..任何想法如何实现？我认为这可能是我对我以前的问题的第一步。我刚开始和Haskell一起玩，所以我没有明白。非常感谢。我可以在红黑树中插入未排序的数据吗？

insertSet x s = T B a y b 
    where ins E = T R E x E 
     ins [email protected](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)

来源

2011-06-05 vis

如果树中的数据未排序，那么该树不再是二叉搜索树。你会如何发现一个元素是否已经在树中（没有经过所有元素）？如果你不希望数据被排序，那么你可能不想要一棵红黑树。 – Cedric 2011-06-05 14:47:47

红黑树是为BST打算，但我想我们可以有一个未分类的二叉树，在这里我想使用相同的RB树的概念来保持它的平衡..应该有一种方法来保持一个未分类的二叉树平衡？ – vis 2011-06-05 15:02:11

当然，关于平衡的棘手问题是保持元素排序。如果你不关心树中元素的顺序，你可以任何你想要的方式平衡它。 – Cedric 2011-06-05 15:15:57

，你可以用我在haskellDB RBTree实施， http://hackage.haskell.org/package/RBTree

使用insert功能：

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

饲料它(\_ _ -> LT)功能，那么你可以随时把新的因素最左边的地方。

来源

2011-06-05 15:10:17 Nybble

（因为我在代码中编写了很多文档，它们不会在生成的html页面中显示，您可以阅读源代码以获取更多信息。） – Nybble 2011-06-05 15:12:37

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

回答

相关问题