haskell - 你能用 O(log n) 插入在 Haskell 中实现二叉搜索树吗？

Question

如果我理解正确，在 Haskell 中修改(插入或删除)二叉搜索树 需要复制整棵树，因此实际上它是 O(n)。有没有办法在 O(log n) 中实现它，或者编译器可能会将 O(n) 插入优化为 O(log n) “幕后”？

Answer 1

If I understand correctly, modifying (insertion or deletion) a Binary Search Tree in Haskell requires copying the whole tree, so practically making it being O(n).

您不需要复制整棵树。实际上，让我们使用一个简单的不平衡二叉搜索树，例如:

data Tree a = Node (Tree a) a (Tree a) | Empty deriving (Eq, Show)

然后我们可以插入一个值:

insertIn :: Ord a => a -> Tree a -> Tree a
insertIn x = go
  where go Empty = Node Empty x Empty
        go n@(Node l v r)
          | x < v = Node (go l) v <b>r</b>
          | x > v = Node <b>l</b> v (go r)
          | otherwise = n

这里我们重用 r 以防我们构造一个Node (go l) v r，我们重用 l 以防我们构造一个节点 l v (go r)。对于我们访问的每个节点，我们创建一个新节点，其中两个子树之一用于新节点。这意味着新树将指向与原始树相同的子树对象。

在这个例子中，新节点的数量因此随着 O(d) 和 d 树的深度而变化。如果树相当平衡，那么它将插入 O(log n)。

当然你可以通过在节点中存储更多关于平衡的信息来改进算法并定义AVL树或红黑树，这样你就可以保证插入O(log n)时间。

这里所有数据都是不可变的事实有助于重用部分树:我们知道 l 和 r 不能改变，所以这两棵树将共享一个如果您想同时使用原始树和新树，则会减少大量节点，从而减少所需的内存量。

如果没有必要引用旧树，垃圾收集器最终将收集已被新树替换的“旧”节点。