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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

没有旋转操作的平衡树——朝鲜树  

2012-11-08 16:21:27|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
众所周知,平衡树一般都是用旋转操作来维护树的平衡。
如果不想写旋转操作而且题目卡时不是很紧的时候肿么办呢?!!

某天albus YY出来了一个没有旋转操作的平衡树,由于albus的真名听起来很像朝鲜主席,所以就叫朝鲜树了!

朝鲜树的查询和删除都和裸BST是一样的,插入元素的时候略有不同。
往朝鲜树插入一个元素时,先把它丢到树里去,然后看看这个节点离根的深度是不是大于了L,如果是,就暴力重建成一棵平衡树。
暴力重建后,树的深度变为了O(logn)
求极值可以得到,对于随机数据,取L = sqrt(n)时最优。
然后插入、查询、删除的时间复杂度都是O(sqrt(n))了……

不过我将L强行设为500。

经过测试,朝鲜树对于随机数据与splay几乎没有差别,但是人为构造的坑爹数据,朝鲜树就会比splay略慢一点点。
我写的朝鲜树代码247行,splay代码231行……代码没有splay短。
朝鲜树实现简单,不过splay实现也很简单……

总之除了没有旋转操作,貌似没任何优点了……
大概没有旋转操作的平衡树也顶多只能做到这样了。

update: 事实上代码可以更简洁……father是不用存的……
update: 我们伟大主席fotile96教导我们,替罪羊树也不用旋转,也是暴力重建,代码也很简洁!均摊O(logn)!听替罪羊树这个喜感的名字是不是很有兴趣呢?可以google Scapegoat Tree。
  评论这张
 
阅读(2469)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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