1.AVL Tree&Splay Tree
约 1264 个字 14 张图片 预计阅读时间 4 分钟
AVL Tree¶
1. balance factor(BF)¶
Order property:左边小,右边大;
Structure property:|BF|<= 1;
与堆相反, 应该先满足Order property;
2. 定义¶
平衡二叉搜索树:balanced binary search tree(BBST) = AVL tree。
高度的定义:空节点的高是1,叶节点高为0,否则就是儿子中高的最大值+1。
3. 为什么要AVL Tree¶
推论
定理:有n个结点的平衡二叉树,是一个斐波那契数列,最后求得高度不高于\(O(logn)\).
证明:先证明引理->任何高度为h的平衡二叉树的结点数小于\(c^h\)(其中\(c\)是一个常数)
而这个性质很容易维护,所以就有了AVL Tree。
4. Rotation 操作¶
4.1 right rotation¶
- 只需要改三个指针,所以时间是O(1);
- 旋转能够维持BST性质;
- 旋转会改变高度差,即会改变BF;
4.2 left rotation¶
5. Insertion¶
5.1 Left case¶
LLcase(LLRotation)¶
LRcase(LRRotation)¶
5.2 Right case¶
5.3 总结¶
只要修正了最下面那个节点,其他因他而起的不平衡节点都会被修正。
插入引起的不平衡最多两次旋转就能修正。
case的划分就是破坏者和被破坏者的关系,找的是被破坏者以下的三层,下面的不用看。
不管是这四种的什么情况,最后都要变成中间一个两边各一个的情况,剩下的四块按顺序搬运过去。
6. Deletion¶
- 步骤:
- 像BST一样delete;
- 恢复平衡;
-
在结构上必定会删除一个leaf;
-
删除只会让一个点变得不平衡,但是修复不平衡时候,旋转一次可能会把不平衡向上传,一直传到根结点为止。所以最多旋转\(O(logn)\)次才能修复,所以最终时间还是为\(O(logn) + O(logn)* O(1) = O(logn)\)。
7. 总结¶
综上所述,AVL树的高度是\(logn\)级别的,并且维持树平衡的代价也是\(logn\)级别的。
Splay Trees¶
1. 核心思想¶
- 不要求每一步都做得很好,但是平均下来时间复杂性要小于等于\(O(logn)\)。
- 要找一个对象(其实是任何一个动作,包括插入),那就顺便把这个对象翻到树根(这样下次查找到他的概率就会大一点)。
2. 不好的情况¶
3. 优化¶
变换过程中不一定两边高度差不超过1;
4. 删除¶
- 找到要删除的节点X,将它旋转到跟节点上(Find X);
- 把跟节点删除,产生左右两颗子树(Remove X);
- 在左子树上找到最大的节点并将他旋转到根节点上(FindMax( \(T_L\) ));
- 把右子树接到左子树根的右边(根已经是最大的了,不可能有右孩子);
Amortized Analysis(均摊代价分析)¶
点此跳转
定义¶
- Amortized Bound:任意多次操作的时间复杂性上界;
- Average-case Bound:无限多次操作的时间复杂性上界;
解决方法¶
Aggregate analysis(累计分析)¶
以push,pop,multipop为例,n次操作,最多只有n个元素,所以mutipop最多也是\(O(n-1)\),所以总时间复杂性就是\(O(n)\),所以每个的时间就是\(O(1)\)。
Accounting method(记账方法)¶
总的时间等于push的两倍
摊还时间 = 实际时间 + credit
在假设了一个要证明的均摊复杂度后,对实际的每步操作,如果实际消耗比均摊消耗低,那么把差值作为“余额”存起来,余额可以为其他操作中实际消耗比均摊消耗高出的那部分“付款”。最后只需要证明每一步的均摊消耗之和大于等于实际消耗之和。(from JerryG 20级)
操作 | 实际代价 | 摊还代价 |
---|---|---|
push | 1 | 2 |
pop | 1 | 0 |
multipop | min(k,s) | 0 |
总和方法对所有的操作一视同仁,而记账算法不同,每个操作的credit不尽相同。
我们可以把摊还代价设置成这样是因为pop次数之和肯定不会超过push的次数,因此可以保证任何情况下信用值不是负数,而此时摊还代价总和的上界为2n所以平均的摊还代价是O(1)。(from 小角龙)
Potential method(势能法)¶
点此跳转
核心:让消耗大的那一步操作势能大大的降!
对账目分析法的一种形式上的改进。定义数据结构自身状态的“势能”函数, 每次操作可能改变自身的势能,势能的改变跟跟余额的改变(每一步均摊和实际的差值)有密切关系,或者说相等。势能最开始取最小值,每一步中,势能增加量等于均摊消耗比实际消耗多出的部分。定义完势能函数后,均摊复杂度一定是大于势能函数每一步的最大可能的增长值的,所以要定义增长尽量缓慢的势能函数,同时又能表现实际操作和均摊操作的关系(这里不太容易说清楚)。势能函数的最大值往往决定了均摊分析的结果。(JerryG 20级)
分析伸展树¶
点此跳转
-
每个结点的势能计算。
Quote
- ADS01AVL_Stu.ppt
- 小角龙(18)复习笔记.pdf
- JerryG(20)复习笔记.pdf
- 智云课堂:2023myc,2022hqm,2022yds
评论
本文总阅读量次