Day2平衡树笔记

线段树不支持的操作：删除，插入

常见的平衡树

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的右孩子