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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

2655
来自专栏数据处理

leetcode222求完全二叉树节点个数

3714
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1171
来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

1071
来自专栏Java 源码分析

二叉树

1.二叉树的性质 1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点 2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点 3.度...

2734
来自专栏灯塔大数据

每周学点大数据 | No.25二叉搜索树回顾(二)

No.25期 二叉搜索树回顾(二) Mr. 王:既然提到了有序的状态,那么我们就来谈谈有根树的遍历问题。 小可:我知道,遍历就是访问一个数据集合中的所...

3496
来自专栏算法channel

基本算法|图解各种树(二)

01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

2875
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

1012
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

1021
来自专栏swag code

Calendar类-set()方法的延时操作

set(f,value)方法将日历字段f更改为value,此外还设置了一个内部成员变量,

722

扫码关注云+社区

领取腾讯云代金券