Dav*_*vid 8 complexity-theory haskell referential-transparency
在查看文档时Data.Set,我看到在树中插入元素被称为O(log(n)).但是,我会直观地期望它是O(n*log(n))(或者可能是O(n)？),因为参照透明度需要在O(n)中创建前一个树的完整副本.
据我所知,例如(:)可以将O(1)代替O(n),因为这里不必复制完整列表; 新的列表可以由编译器优化为第一个元素加上指向旧列表的指针(请注意,这是一个编译器 - 而不是语言级别 - 优化).但是,在a中插入一个值Data.Set涉及重新平衡,这对我来说非常复杂,我怀疑有类似于列表优化的东西.我尝试阅读Set docs引用的论文,但无法用它来回答我的问题.
那么:如何在一个(纯)函数式语言中将元素插入二叉树中是O(log(n))？
sel*_*pou 16
没有必要制作a的完整副本Set以便在其中插入元素.在内部,元素存储在树中,这意味着您只需要沿插入路径创建新节点.可以在插入前和插入后版本之间共享未触及的节点Set.正如Deitrich Epp所指出的,在平衡树中O(log(n))是插入路径的长度.(抱歉忽略这个重要的事实.)
说你的Tree类型如下:
data Tree a = Node a (Tree a) (Tree a)
| Leaf
...并说你有一个Tree看起来像这样的人
let t = Node 10 tl (Node 15 Leaf tr')
...在哪里tl和tr'是一些命名的子树.现在说你要插入12这棵树.嗯,这看起来像这样:
let t' = Node 10 tl (Node 15 (Node 12 Leaf Leaf) tr')
子树tl和tr'被共享t和t',你只需要建造3个新的Nodes去做,即使规模t可能会比3大得多.
编辑:重新平衡
关于重新平衡,请考虑这样,并注意我在这里没有严格要求.假设你有一棵空树.已经平衡了!现在说你插入一个元素.已经平衡了!现在说你插入另一个元素.嗯,有一个奇数,所以你不能做那么多.
这是棘手的部分.假设您插入另一个元素.这可以有两种方式:左或右; 平衡或不平衡.如果它不平衡,您可以清楚地执行树的旋转以平衡它.如果它是平衡的,已经平衡!
这里要注意的重要一点是你不断重新平衡.它不像你有一堆树,决定插入一个元素,但在你这样做之前,你重新平衡,然后在你完成插入后留下一团糟.
现在说你继续插入元素.树会变得不平衡,但不是很多.当这种情况发生时,首先你要立即纠正,然后,沿着插入的路径进行校正,这是O(log(n))在一个平衡的树中.您链接到的纸张中的旋转最多触摸树中的三个节点以执行旋转.所以你O(3 * log(n))在重新平衡时正在做的工作.那还是O(log(n)).
为了更加强调dave4420在评论中所说的内容,(:)在常量运行中不会涉及编译器优化.您可以实现自己的列表数据类型,并在一个简单的非优化Haskell解释器中运行它,它仍然是O(1).
列表被定义为初始元素加上一个列表(或者在基本情况下它是空的).这是一个等同于本机列表的定义:
data List a = Nil | Cons a (List a)
因此,如果你有一个元素和一个列表,并且你想用它们构建一个新的列表Cons,那就是直接从构造函数所需的参数创建一个新的数据结构.甚至不需要检查尾部列表(更不用说复制它),而是在执行某些操作时检查或复制字符串Person "Fred".
当你声称这是编译器优化而不是语言级优化时,你就错了.此行为直接来自列表数据类型的语言级别定义.
同样,对于定义为项目加上两棵树(或空树)的树,当您将项目插入非空树时,它必须位于左侧或右侧子树中.您需要构造包含该元素的该树的新版本,这意味着您需要构建一个包含新子树的新父节点.但是其他子树根本不需要遍历; 它可以按原样放入新的父树中.在平衡树中,这是可以共享的树的一半.
递归地应用这种推理应该表明实际上根本不需要复制数据元素; 在路径上只需要新的父节点,直到插入元素的最终位置.每个新节点存储3件事:一个项目(直接与原始树中的项目引用共享),一个未更改的子树(直接与原始树共享),以及一个新创建的子树(几乎所有子结构都与原始子树共享)树).在平衡树中将有O(log(n)).