特价做网站,17zwd一起做网店潮汕站,一个网站做数据维护需要多久,a做爰视频免费观费网站替罪羊树详解
刚开始学习平衡树。可是我太弱了弄不懂有旋转操作的treap和splay#xff0c;这时候学习可以不用旋转操作——替罪羊树的平衡树就很适合。这个名字取得比较玄乎#xff0c;一眼看上去并不知道有什么卵用#xff0c;但是#xff0c; 如果你是刚学平衡树的新手这时候学习可以不用旋转操作——替罪羊树的平衡树就很适合。这个名字取得比较玄乎一眼看上去并不知道有什么卵用但是 如果你是刚学平衡树的新手那么从替罪羊树开始学一定是个绝佳的选择因为它是个很优雅的平衡树什么叫优雅暴力即是优雅
如果在一棵平衡的二叉搜索树内进行查询等操作时间就可以稳定在log(n)但是每一次的插入节点和删除节点都可能会使得这棵树不平衡最坏情况就是退化成一条链显然我们不想要这种树于是各种维护的方法出现了大部分的平衡树都是通过旋转来维护平衡的但替罪羊树就很厉害了一旦发现不平衡的子树立马拍扁重建这就是替罪羊树的核心暴力重建
先来说说我的替罪羊树上的每个节点包含些什么
1 zuo,you记录该节点的左右儿子
2x该节点的值
3tot有多少个值为x的数
4 size,trsize,whsizesize表示以该节点为根的子树内有多少个节点trsize表示有多少个有效节点这个后面再讲啦whsize表示有多少个数也就是子树内所有节点的tot的和
5fa该点的父亲
6tf该点是否有删除标记这个也会在后面讲啦
用处
替罪羊树是一种平衡树支持插入删除查找第k小元素查找元素的排名等操作
1、关于α
在替罪羊树中定义了一个平衡因子αα的范围因题而异一般取0.5~1.0之间若题目没有特殊说明一般就取个中0.75就好了。那这个α有啥用呢替罪羊树判断一棵子树是否平衡的方法是如果 x的左右子树的节点数量 以x为根的子树的节点数量α 那么以x为根的这棵子树就是不平衡的。显然的如果有一棵子树的大小超过了 以x为根的子树的节点数量α那么这种节点一边倒的情况对于查询来说肯定就很慢所以这个时候我们就将它重建。 不知各位有木有想过α的值究竟与效率有什么关系呢仔细想想当α的值越小那么替罪羊树就越容易重构那么树也就越平衡查询的效率也就越高自然修改加点和删点的效率也就低了所以如果查询操作比较多的话就可以将α的值设小一点反之假如修改操作多自然α的值就要大一点了。
还有α不能等于1 or 0.5假如它等于0.5那么当一棵树被重构之后如果因为节点数问题不能完全重构成一个完全二叉树那么显然对于这棵树的根他的 | 左子树节点数量 - 右子树节点数量 | 很可能会等于1那么如果往多的那棵子树上加一个节点那么这棵树又得重构一次最坏情况时间会变成n^2显然死定了。。那么等于1会怎么样还能怎么样你觉得会有一棵子树的大小大于整棵树的大小吗
2、关于时间复杂度
除了重构操作其他操作的时间复杂度显然都是log(n)的那么下面看一下重构的时间复杂度。
虽然重构一次的时间复杂度是O(n)的但是均摊下来其实只是O(logn)。
考虑极端情况每次都把整棵树重构。
那么我们就需要每次都往根的一棵子树内加点假设一开始是平衡的那么左右子树各有50%的节点那么要使一棵子树内含有超过75%的节点那么这棵子树就需要在原来的基础上增加2倍的节点数。也就是说当最差情况时整棵替罪羊树的节点数要翻个倍才会重构。那么最差情况时也就是在4,8,16,32……个节点时才会重构于是重构的总的时间复杂度也就是O(nlogn)了加上一些杂七杂八的重构也不过就是加上一个很小的常数可以省略不计。所以替罪羊树的时间复杂度依然是O(nlogn)的。 引用博客一、结构体指针 二、树状数组 三、带图更清晰
