线段树不支持的操作：删除，插入
常见的平衡树
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的右孩子
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
