没有合适的资源?快使用搜索试试~ 我知道了~
ACM 程序设计:伸展树-p6.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 123 浏览量
2022-06-18
20:50:29
上传
评论
收藏 1.1MB PDF 举报
温馨提示
试读
17页
ACM 程序设计:伸展树-p6.pdf
资源推荐
资源详情
资源评论
2014/4/16
1
华南师大讲稿
伸展树
ACM程序设计实训(二)
华南师大讲稿
二叉树问题
35
15 45
50
40
25
10
20
30
树1
35
15 45
50 40 25 10
20
30
树2
华南师大讲稿
二叉排序树的应用
1.排序操作
2.查找第k个最小元素
华南师大讲稿
查找第k个最小元素
如果需要按位次查找,可在每个结点增加一个新
字段LeftSize,其值为该结点的左子树中的元素个
数加1。
从而可得查找第k个最小元素的算法:
template <class Type>
BstNode<Type>* BST<Type>::Search(int k) {
BstNode<Type> *t = root;
while (t) {
if (k == tLeftSize) return t;
if (k < t LeftSize) t = tLeftChild;
else { k -= LeftSize; t = tRightChild; }
}
return 0;
}
华南师大讲稿
算法分析
假设二叉查找树的高度为h,则无论是按关键字
查找还是按位次查找,在最坏情况下算法的计算时
间为O(h)。
华南师大讲稿
问题描述
分析公司的营业情况是一项相当复杂的工作。经济管理学上
定义了一种最小波动值来衡量营业情况:
每天的最小波动值= min { | 该天以前某一天的营业额-该天
的营业额 | }
第一天的最小波动值为第一天的营业额。
最小波动值越大,说明营业情况越不稳定。要分析整个公司
从成立到现在营业情况是否稳定,只需要把每一天的最小波
动值加起来就可以了。
现在给出公司成立以来每天的营业额,编写一个程序计算
公司成立以来每天的最小波动值的总和。
数据范围:天数
n≤32767
,每天的营业额
ai≤1,000,000
。
最后结果
T≤2
31
。
2014/4/16
2
华南师大讲稿
分析思路
• 根据题目意思,我们发现题目的关键是要每次读入
一个数,并且在前面输入的数中找到一个与该数相
差最小的一个。即要找到与当前输入值最接近的一
个数。
• 解法一:蛮力法
• 每次读入一个数,就讲前面输入的数依次查找一遍,
求出与当前数的最小差值,记入总结果T中。
时间复杂度O(n
2
),不能在时限内出解
华南师大讲稿
2
3
4
5
6
1
2
3
4
5
6
1
3
1
6
2
4
5
3
1
6
2
4
5
华南师大讲稿
伸展树
• 二叉查找树BST能够支持多种动态集合操作,因此在
ACM比赛中,二叉查找树起着非常重要的作用,它可
以用来表示有序集合,建立索引或优先队列等。
• 作用于二叉查找树上的基本操作的时间与树的高度成
正比,当呈线性链结构时,这些操作的运行时间均为
O(n),于是在实际应用中经常做一些变形,让其基本
操作在最坏情况下性能依然很好,如AVL树,但其过
高的编程复杂度却人望而却步。
• 伸展树不是一个新数据结构,而只是改进BST性能
的一组规则
–保证访问的总代价不高,达到最令人满意的性能
–不能保证最终树高平衡
华南师大讲稿
伸展树的性质
• 与二叉查找树一样,伸展树也具有有序性。
即伸展树中的每一个顶点key都满足:该顶点
左子树中的每一个元素都小于key,而其右子
树中的每一个元素都大于key。
• 操作特点:
• 被访问时,删除则其双亲结点做根。
• 其他情况均以该结点为新根。
华南师大讲稿
伸展树的基本操作
• 展开操作,即伸展树自我调整从结点x调整以结点y为双亲的
位置上
• 判断元素key是否在伸展树中
• 将元素key插入到伸展树中
• 将元素key从伸展树中删除
• 从伸展树中删除最小值或最大值
• 将两个伸展树S1与S2合并。其中S1的所有元素都小于S2的所有
元素。
• 以key为界,将伸展树S分离为两棵伸展树S1和S2,其中S1中所
有元素都小于key,S2中的所有元素都大于key。
• 其他操作都是在展开操作的基础上进行的。
华南师大讲稿
2
3
4
5
6
1
2
3
4
5
6
1
3
1
6
2
4
5
3
1
6
2
4
5
2014/4/16
3
华南师大讲稿
存储结构
struct node {
node *lc, *rc, *par;
int val, weight;
} *root;
华南师大讲稿
展开( splaying )
• 每当访问一个结点x时(例如,当x被插入、删除或
者是检索目标时),伸展树就完成一次称为展开
( splaying )的过程
–插入、检索时展开处理把结点x移到BST的根结点
–当删除结点x时,展开过程把结点x的父结点移到根结
点
• 像在AVL树中一样,结点x的一次展开包括一组旋
转( rotation )
–一次旋转通过调整结点x相对于其父结点和祖父结点的
位置,把它移到树结构中的更高层
华南师大讲稿
单旋转( single rotation )
• 当被访问结点是根结点的子女时,完成单旋转,它基本上在保持BST特
性的情况下把结点x与它的父结点交换位置
• 上图一次右旋即可
华南师大讲稿
右旋操作
void Zig (node *x)
{ node *y = x->par;
y->lc = x->rc;
if (x->rc) x->rc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->rc = y;
y->par = x;
} // Zig
华南师大讲稿
左旋操作
void Zag (node *x)
{ node *y = x->par;
y->rc = x->lc;
if (x->lc) x->lc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->lc = y;
y->par = x;
} // Zag
华南师大讲稿
代码的简化
• Zig旋转与Zag旋转算法非常相似
void Zig (node *x)
{ node *y = x->par;
y->lc = x->rc;
if (x->rc) x->rc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->rc = y;
y->par = x;
} // Zig
void Zag (node *x)
{ node *y = x->par;
y->rc = x->lc;
if (x->lc) x->lc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->lc = y;
y->par = x;
} // Zag
2014/4/16
4
华南师大讲稿
存储结构的改写
struct node {
node *child[2], *par;
int val, weight;
} *root;
华南师大讲稿
代码的简化
• Zig旋转与Zag旋转算法非常相似
void Zig (node *x)
{ node *y = x->par;
y->lc = x->rc;
if (x->rc) x->rc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->rc = y;
y->par = x;
} // Zig
void Zag (node *x)
{ node *y = x->par;
y->rc = x->lc;
if (x->lc) x->lc->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->lc)
y->par->lc = x;
else
y->par->rc = x;
} // if
x->lc = y;
y->par = x;
} // Zag
华南师大讲稿
左旋和右旋操作
void turn(node *x,int d)
{ node *y = x->par;
y->child[!d] = x->child[d];
if (x->child[d]) x->child[d]->par = y;
x->par = y->par;
if (y->par) {
if (y == y->par->child[0])
y->par->child[0] = x;
else
y->par->child[1] = x;
} // if
x->child[d] = y;
y->par = x;
} // turn
华南师大讲稿
双旋转( double rotation )
• 双旋转涉及到
–结点x
–结点x的父结点(称为y)
–结点x的祖父结点(称为z)
• 双旋转的结果是把结点x在树结构中向上移两层
华南师大讲稿
• 双旋转分为两类
– 一字形旋转( zigzig rotation ) 右右旋转
• 也称为同构调整(homogeneous configuration);
– 之字形旋转( zigzag rotation ) 右左旋转
• 也称为异构调整(heterogeneous configuration)
华南师大讲稿
一字形旋转
• 当出现以下两种情况之一时,就会发生一字形旋转:
– 1. 结点x是结点y的左子女,结点y是结点z的左子女。
– 2. 结点x是结点y的右子女,结点y是结点z的右子女。
剩余16页未读,继续阅读
资源评论
wxg520cxl
- 粉丝: 24
- 资源: 3万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功