在查看Data.Set的文档时，我看到在树中插入一个元素的时间是O(log(n))。然而，我直观地期望它是O(n*log(n))(或者可能是O(n)?)，因为引用透明性需要在O(n)中创建前一个树的完整副本。
我明白，例如(:)可以制作为O(1)而不是O(n)，因为这里不需要复制完整的列表;编译器可以将新列表优化为第一个元素加上一个指向旧列表的指针(注意，这是编译器而不是语言级别的优化)。然而，在Data.Set中插入一个值涉及到重新平衡，这在我看来相当复杂，以至于我怀疑是否存在类似于列表优化的东西。我试着阅读了Set文档引用的论文，但无法用它来回答我的问题。
那么:在(纯)函数语言中，如何将一个元素插入二叉树是O(log(n)) ?
为了插入一个元素，不需要对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"之类的操作时检查或复制字符串一样。
当你声称这是编译器优化而不是语言级优化时，你完全错了。此行为直接遵循列表数据类型的语言级别定义。
类似地，对于定义为一项加两棵树(或一棵空树)的树，当您将一项插入到非空树中时，它必须在左子树或右子树中。您需要构造一个包含该元素的新版本的树，这意味着您需要构造一个包含新子树的新父节点。但是other子树根本不需要遍历;它可以按原样放在新的父树中。在平衡树中，这是可以共享的树的完整一半。
递归地应用这个推理应该会告诉你，实际上根本不需要复制数据元素;在通往插入元素的最终位置的路径上只需要新的父节点。每个新节点存储3个东西:一个项目(直接与原始树中的项目引用共享)，一个未更改的子树(直接与原始树共享)，以及一个新创建的子树(几乎与原始树共享其所有结构)。在平衡树中会有O(log(n))个这样的树