首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基本算法|图解各种树(四)

基本算法|图解各种树(四)

作者头像
double
发布2018-04-02 15:20:45
5970
发布2018-04-02 15:20:45
举报
文章被收录于专栏:算法channel算法channel

基本算法|图解各种树(一)

基本算法|图解各种树(二)

基本算法|图解各种树(三)

01

局部性

刚被访问过的数据,极有可能很快地再次被访问,这一现象在信息处理过程中屡见不鲜。

例如,推荐系统topk项集的的每一项都有可能被重复地购买,排名靠前的网页被访问后,我们很可能很快就又去访问它。

再如去开学术会议时在012会议室遇到的同门师兄,可能明天又在餐厅相遇。

02

利用局部性

如下的ist,

访问效率关键取决于秩的位置,越靠前的元素,访问的效率越高,

假定的数据具有局部性,我们利用这个特性,访问过秩为i的元素后,将其移动到最前端,很可能紧接着,它有可能被访问到,等再访问时,它就很快被访问到了,

因此,使用一段时间后,最近被访问的元素都跑到list的前面,由于有局部性,因此接着要访问的元素很可能位于前端区域,所以会取得很高的访问效率,

类似地,在二叉树中,同样将刚访问的元素放到前头,

这种BST树就是伸展树,某个刚被访问的节点,通过左右摇摆,逐层伸展到树根位置...

03

伸展

节点v被访问后,立即移到树根位置,借助的手段依然是zig和zag操作,

04

Tarjan点睛

构思的精髓是向上追溯两层,而非一层。反复考察祖孙三代,经过两次旋转,使v上升两层。

向上伸展两层,看看最坏情况下,树的折叠效果,访问最下节点1,考虑祖孙三代,

当节点1达到树根时,树的高度差不多变为原来的一半,而逐层伸展的话,树高不变,所以tarjan的两层伸展是更好的。

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:基本算法,机器学习,深度学习,Kaggle实战,Spark和Tensorflow等。期待您的到来!

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-01-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档