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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

平衡树系列专题  

2014-04-03 20:23:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//最近刚学完平衡树,为了加深印象,发一篇blog加强印象。(话说我学习的顺序有点奇怪,别人都是先学主席树什么的,我直接先平衡树上了= =)

平衡树是一种排序二叉树(Binary Search Tree,BST),BST每个节点保存了一个值域(如数,字符串什么的,这个值域叫做键值),满足对于所有的节点,左子树中的节点的值都比它小,右子树中的节点都比它大。于是,对一棵BST做中序遍历就得到了一个排好序的序列。BST的效率取决于树高,对于随机数据,BST的期望复杂度是O(log2N),但是可能会出现某些不太好的状况,比如……变成一条链(⊙﹏⊙b汗),那这棵BST就废掉了……这样称作BST的退化,我们要防止这种情况的发生。

但是,插入节点的方式是唯一的,插入节点的顺序并不是你可以控制的(这取决于使用者)。

该如何防止退化呢?通过旋转!

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

可以发现,旋转不破坏平衡树的性质,于是,我们通过旋转来保持树的平衡,平衡的BST叫做平衡树

常见的平衡树有Treap,Splay,红黑树以及AVL树等等(后两者为严格的平衡二叉树,树高严格控制在log2N)

由于后两种过于复杂,所以暂时不介绍(明显是我太弱不会写= =),这里介绍两种应用较为广泛,代码简单的Treap和Splay。

//由于平衡树比较复杂,百度空间居然有长度限制!!!于是得放在几篇blog里分别看= =

传送门:

平衡树系列专题之一:Treap

平衡树系列专题之二:Splay

平衡树系列专题之三:AVL树

//由于我太弱,不会AVL树,于是链接到一个我认为写的清楚的blog里去= =

//终于码完了囧,感觉splay写的异常渣,自己都快看不懂了= =


入门练习题:

bzoj 3224:普通平衡树,treap的简单应用。

bzoj 3223:文艺平衡树,splay维护区间的简单应用。

bzoj 3296:二逼平衡树,线段树套平衡树,树套树的入门。

练习题:

bzoj 1588:营业额统计,treap(或splay)找前驱后继

bzoj 1056(1862):排名系统,map(hash)+splay维护区间

bzoj 1861:书架,splay维护区间

bzoj 1269(1507):文本编辑器,splay维护区间

bzoj 1500:维修序列,splay维护区间,要维护的东西很多。

基本上差不多了吧,终于刷完平衡树的题目了,下面……学AC自动机好了

  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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