内容发布更新时间 : 2024/5/3 10:40:20星期一 下面是文章的全部内容请认真阅读。

IOI2005国家集训队论文 黄源河

最后，由于right(A) 的距离可能发生改变，我们必须更新A的距离：

dist(A) ← dist(right(A)) + 1

不难验证，经这样合并后的树C符合性质1和性质2，因此是一棵左偏树。至此左偏树的合并就完成了。

下图是一个合并过程的示例：

合并流程

第 6 页 共 21 页

IOI2005国家集训队论文 黄源河

我们可以用下面的代码描述左偏树的合并过程：

Function Merge(A, B) If A = NULL Then return B If B = NULL Then return A If key(B) < key(A) Then swap(A, B) right(A) ← Merge(right(A), B) If dist(right(A)) > dist(left(A)) Then swap(left(A), right(A)) If right(A) = NULL Then dist(A) ← 0 Else dist(A) ← dist(right(A)) + 1 return A End Function

下面我们来分析合并操作的时间复杂度。从上面的过程可以看出，每一次递归合并的开始，都需要分解其中一棵树，总是把分解出的右子树参加下一步的合并。根据性质3，一棵树的距离决定于其右子树的距离，而右子树的距离在每次分解中递减，因此每棵树A或B被分解的次数分别不会超过它们各自的距离。根据性质4，分解的次数不会超过?log(N1+1)? + ?log(N2+1)? -2，其中N1和N2分别为左偏树A和B的节点个数。因此合并操作最坏情况下的时间复杂度为O( ?log(N1+1)? + ?log(N2+1)? -2) = O(log N1 + log N2)。

3.2 插入新节点

单节点的树一定是左偏树，因此向左偏树插入一个节点可以看作是对两棵左偏树的合并。下面是插入新节点的代码：

Procedure Insert(x, A) B ← MakeIntoTree(x) A ← Merge(A, B) End Procedure

由于合并的其中一棵树只有一个节点，因此插入新节点操作的时间复杂度是O(logn)。

第 7 页 共 21 页

IOI2005国家集训队论文 黄源河

3.3 删除最小节点

由性质1，我们知道，左偏树的根节点是最小节点。在删除根节点后，剩下的两棵子树都是左偏树，需要把他们合并。删除最小节点操作的代码也非常简单：

Function DeleteMin(A) t ← key(root(A)) A ← Merge(left(A), right(A)) return t End Function

由于删除最小节点后只需进行一次合并，因此删除最小节点的时间复杂度也为O(logn)。

3.4 左偏树的构建

将n个节点构建成一棵左偏树，这也是一个常用的操作。

算法一 暴力算法——逐个节点插入，时间复杂度为O(nlogn)。

算法二 仿照二叉堆的构建算法，我们可以得到下面这种算法： ? 将n个节点（每个节点作为一棵左偏树）放入先进先出队列。 ? 不断地从队首取出两棵左偏树，将它们合并之后加入队尾。 ? 当队列中只剩下一棵左偏树时，算法结束。

1

2 3 4 5 6

3 4 5 6 1 第 8 页 共 21 页

2 IOI2005国家集训队论文 黄源河

5 6 1 2 3 4 1 2 3 4 5 6 6 6 5 3 4 2 1 3 4 2 1 5 构建流程

下面分析算法二的时间复杂度。假设n=2k，则：

n次和并的是两棵只有1个节点的左偏树。 2n接下来的次合并的是两棵有2个节点的左偏树。

4n接下来的次合并的是两棵有4个节点的左偏树。

8??

n接下来的i次合并的是两棵有2i-1个节点的左偏树。

2前

合并两棵2i个节点的左偏树时间复杂度为O(i)，因此算法二的总时间复杂

knnnik?2度为：*O(1)?*O(2)?*O(3)???O(n*?i)?O(n*(2?k))?O(n)。

2482i?12

3.5 删除任意已知节点

接下来是关于删除任意已知节点的操作。之所以强调“已知”，是因为这里

所说的任意节点并不是根据它的键值找出来的，左偏树本身除了可以迅速找到最小节点外，不能有效的搜索指定键值的节点。故此，我们不能要求：请删除所有键值为100的节点。

前面说过，优先队列是一种容器。对于通常的容器来说，一旦节点被放进去以后，容器就完全拥有了这个节点，每个容器中的节点具有唯一的对象掌握它的

第 9 页 共 21 页

IOI2005国家集训队论文 黄源河

拥有权（ownership）。对于这种容器的应用，优先队列只能删除最小节点，因为你根本无从知道它的其它节点是什么。

但是优先队列除了作为一种容器外还有另一个作用，就是可以找到最小节点。很多应用是针对这个功能的，它们并没有将拥有权完全转移给优先队列，而是把优先队列作为一个最小节点的选择器，从一堆节点中依次将它们选出来。这样一来节点的拥有权就可能同时被其它对象掌握。也就是说某个节点虽不是最小节点，不能从优先队列那里“已知”，但却可以从其它的拥有者那里“已知”。

这种优先队列的应用也是很常见的。设想我们有一个闹钟，它可以记录很多个响铃时间，不过由于时间是线性的，铃只能一个个按先后次序响，优先队列就很适合用来作这样的挑选。另一方面使用者应该可以随时取消一个“已知”的响铃时间，这就需要进行任意已知节点的删除操作了。

我们的这种删除操作需要指定被删除的节点，这和原来的删除根节点的操作是兼容的，因为根节点肯定是已知的。上面已经提过，在删除一个节点以后，将会剩下它的两棵子树，它们都是左偏树，我们先把它们合并成一棵新的左偏树。

p ← Merge(left(x), right(x))

现在p指向了这颗新的左偏树，如果我们删除的是根节点，此时任务已经完成了。不过，如果被删除节点x不是根节点就有点麻烦了。这时p指向的新树的距离有可能比原来x的距离要大或小，这势必有可能影响原来x的父节点q的距离，因为q现在成为新树p的父节点了。于是就要仿照合并操作里面的做法，对q的左右子树作出调整，并更新q的距离。这一过程引起了连锁反应，我们要顺着q的父节点链一直往上进行调整。

q x p q

新树p的距离为dist(p)，如果dist(p)+1等于q的原有距离dist(q)，那么不管p是q的左子树还是右子树，我们都不需要对q进行任何调整，此时删除操作也就完成了。

如果dist(p)+1小于q的原有距离dist(q)，那么q的距离必须调整为dist(p)+1，而且如果p是左子树的话，说明q的左子树距离比右子树小，必须交换子树。由于q的距离减少了，所以q的父节点也要做出同样的处理。

剩下就是另外一种情况了，那就是p的距离增大了，使得dist(p)+1大于q的原有距离dist(q)。在这种情况下，如果p是左子树，那么q的距离不会改变，

第 10 页 共 21 页