在查看 的文档时Data.Set，我看到将元素插入树中被提到为 O(log(n))。但是，我直觉上希望它是 O(n*log(n))（或者可能是 O(n)？），因为引用透明性需要在 O(n) 中创建前一棵树的完整副本。
我知道例如(:)可以使 O(1) 而不是 O(n)，因为这里不必复制完整列表；编译器可以将新列表优化为第一个元素加上指向旧列表的指针（请注意，这是编译器 - 不是语言级别的 - 优化）。但是，将值插入 aData.Set涉及重新平衡，这对我来说看起来很复杂，以至于我怀疑是否存在类似于列表优化的东西。我尝试阅读Set docs 引用的论文，但无法用它回答我的问题。
那么：在（纯）函数式语言中，如何将元素插入二叉树是 O(log(n))？
无需制作 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')
子树tland在andtr'之间共享，您只需要构造 3 个 new即可，即使 的大小可能远大于 3。tt'Nodest
编辑：再平衡
关于再平衡，请这样想，并注意我在这里并不严谨。假设你有一棵空树。已经平衡了！现在说你插入一个元素。已经平衡了！现在假设您插入另一个元素。嗯，有一个奇数，所以你不能在那里做很多事情。
这是棘手的部分。假设您插入另一个元素。这可以有两种方式：向左或向右；平衡或不平衡。在不平衡的情况下，您可以清楚地执行树的旋转来平衡它。在它平衡的情况下，已经平衡了！
这里需要注意的重要一点是，您一直在重新平衡。这不像你有一棵树，决定插入一个元素，但在你这样做之前，你重新平衡，然后在你完成插入后留下一团糟。
现在说你继续插入元素。树会变得不平衡，但不会太多。当这种情况发生时，首先你要立即纠正它，其次，纠正发生在插入的路径上，它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)) 个。