Day2平衡树笔记

2018-06-17 21:39:24来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

线段树不支持的操作:删除,插入


 

常见的平衡树

treap 慢||好写

sbt(大小平衡的树) 非常快 比较好写 ||功能不全

rbt 红黑树 特别快 || 非常难写  

以上操作支持插入删除O(NlogN)

splay 特别慢。。≈O(sqrt(N))

不太好写,功能强大


 

可持久化Treap

平衡树一定是二叉树

左儿子里面的元素一定比他小

右儿子一定比当前节点大

中序遍历一定排好序

每次递归的查询

小——》左

大——》右

弊端:深度可能会非常深-->代价非常大

 


 

Treap=Tree+heap

 

treap:存两个值[key,val]

val:每次插入的值,满足平衡树的性质

key:满足堆的性质,直接rand,深度一定是logN级别的

 

merge(p1,p2):把以p1为根的Treap和以P2为根的Treap合并成一个Treap,p1的最大值应该<=P2的最小值

split(p,k):把以p为根的Treap拆成两个Treap,一个有k个数,另一个有n-k个数,k为前k小

插入:先把树分为x,y两部分,然后把新的节点a看做是一棵树,先与x合并,合并完之后将合并的整体与y合并

删除:

 

 

merge实现

先找key最大的,比较p1,p2

  • 若p1大

p1作为根,p2一定在p1的右边,

p1.L=p1.L

p1.r=merge(p2,p1.r)

  • 若p2

p2.r=p2.r

p2.L=merge(p2.L,p1)

merge返回的是根节点

 

split实现

size:子树有多少个节点

当k<=p.L.size—>split(p.L,k)—>设p1为有用的子树,那么直接merge(p2,p.r)就好,把p2作为p的左孩子

当k==p.L.size+1 返回p.L+p,p.r

当k>p.L.size+1—>split(p.r,k-p.L.size-1)—>设p2为有用的子树,直接merge(p,p1),把p1作为p的右孩子

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:二维数组的指针指向记录

下一篇:洛谷 P3386 【模板】二分图匹配 Dinic版