内容发布更新时间 : 2024/12/23 12:33:59星期一 下面是文章的全部内容请认真阅读。
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 页