gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-05 02:34:27 25 4
gpt4 key购买 nike

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

最佳答案

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)时间。

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

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

关于haskell - 你能用 O(log n) 插入在 Haskell 中实现二叉搜索树吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70754190/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com