注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

平衡树系列专题之二:Splay  

2014-04-07 18:40:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

splay(伸展树)的出发点是这样的:考虑到局部性原理(刚被访问的内容下次可能仍会被访问,查找次数多的内容可能下一次会被访问),为了使整个查找时间更小,被查频率高的那些节点应当经常处于靠近树根的位置。这样,很容易得想到以下这个方案:每次查找节点之后对树进行重构,把被查找的节点搬移到树根,这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后,它均会通过旋转的方法把被访问节点旋转到树根的位置。

对于连续重复的操作,splay有很好的效率。


splay的最重要的操作是伸展操作,它支持把一个节点x,向上提升到根,方式当然还是旋转


注:通常情况下,会把left_rotate简写成Zag,right_rotate简写成Zig

为了方便起见,我们把要提的点设为x,x的父亲设为y,y的父亲设为z。


具体的将,对于一个节点x,会分三种情况考虑

情况一:x的父节点为根节点,则进行一次单旋即可

平衡树系列专题之二:Splay - mxh1999 - 一个蒟蒻的代码回收站

情况二:x的父节点不是根节点,且x,y,z共线,则需要两次方向相同的单旋

平衡树系列专题之二:Splay - mxh1999 - 一个蒟蒻的代码回收站

情况三:x的父亲不是根节点,且x,y,z不共线,则需要两次方向相反的单旋。

平衡树系列专题之二:Splay - mxh1999 - 一个蒟蒻的代码回收站

反复执行以上操作,直到x变成根。

放出伸展操作的代码:


void splay(int x,int s)
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017