大气装饰装修企业网站模版源码,可以免费做网站,山东省建设局拖欠工资网站,百度权重查询网址二叉搜索树
任一节点x的左/右子树中#xff0c;所有非空节点均不大于#xff08;不小于#xff09;x
必须是所有的非空节点#xff0c;仅左右孩子不够#xff08;左孩子的右孩子可能很大#xff09;一棵二叉树是二叉搜索树当且仅当中序遍历序列是单调非降序列
两棵二叉…
二叉搜索树
任一节点x的左/右子树中所有非空节点均不大于不小于x
必须是所有的非空节点仅左右孩子不够左孩子的右孩子可能很大一棵二叉树是二叉搜索树当且仅当中序遍历序列是单调非降序列
两棵二叉搜索树等价当且仅当他们有相同的中序遍历序列上下可变左右不乱
换言之构成两棵二叉搜索树的元素相同
等价变换zig、zag
zig右单旋转zag左单旋转
变换后仍保持二叉搜索树的性质 《算法导论》练习13.2-2在任何一棵有n个结点的二叉搜索树中恰有n-1种可能的旋转。 度为2的节点有2种转法度为1的节点有1种转法从而每种旋转对应一条边共n-1条边。 《算法导论》练习13.2-4任何一棵含n个结点的二叉搜索树可以通过O(n)次旋转转变为其他任何一棵含n个结点的二叉搜索树。 对于任何含n个结点的二叉搜索树若某节点有左孩子就右旋如此会消除一个左孩子-父节点关系而最多只有n-1个上述的左孩子-父节点关系从而经至多n-1次旋转就能将其变为一条右链而左右旋都是可逆的转变只需要以该右链作为中介。 【2014-THU-Fin】由同一组共n个词条构成的任意两棵BST经O(logn)次zig和zag旋转之后必可相互转换。× 搜索
中序遍历操作
内部变量_hot指向搜索的终止位置的父节点
如果命中就是目标节点的父节点如果未命中就是目标节点如果存在时的父节点
API返回搜索的终止位置
如果命中就是目标节点如果未命中就是_hot的子哨兵节点
时间复杂度O(h)
插入
先搜索让_hot指向将增加孩子的节点再添加子节点
从插入的节点开始向上更新节点高度
时间复杂度O(h)
删除
单子节点删除
直接把删除节点换成其以子唯一节点为根的子树
删除时利用搜索接口确定节点位置的过程给出当前_hot它是向上更新节点高度的起点
双子节点删除
用在右子树中的直接后继替换删除节点原来直接后继是度不为2的节点化为单子节点删除
_hot设为原来直接后继的父节点它是向上更新节点高度的起点
/******************************************************************************************
* BST节点删除算法初除位置x所指癿节点全局静态模板函数适用亍AVL、Splay、RedBlack等各种BST
* 目标x在此前经查找定位并确认非NULL故必删除成功与searchIn不同调用之前不必将hot置空
* 返回值指向实际被删除节点的接替者hot指向实际被删除节点的父亲——二者均有可能是NULL
******************************************************************************************/
template typename T
static BinNodePosi(T) removeAt (BinNodePosi(T) x, BinNodePosi(T) hot) {BinNodePosi(T) w x; //实际被摘除的节点初值同xBinNodePosi(T) succ NULL; //实际被删除节点的接替者if (!HasLChild(*x)) { //若*x的左子树为空则可succ x x-rc; //直接将*x替换为其右子树}else if (!HasRChild(*x)){ //若右子树为空则可succ x x-lc; //对称地处理——注意此时succ ! NULL}else { //若左右子树均存在则选择x的直接后继作为实际被摘除节点为此需要w w-succ(); //在右子树中找到*x的直接后继*wswap(x-data, w-data); //交换*x和*w的数据元素BinNodePosi(T) u w-parent;succ w-rc; //w一定无左孩子化为单节点的仅有右孩子情形((u x) ? u-rc : u-lc) succ;//如果u是x即x是w的父节点此时w在u的右子树中//若不然因w是x的直接后继此时w在u的左子树中}hot w-parent; //记录实际被删除节点的父亲if (succ) {succ-parent hot; //并将被删除节点的接替者与hot相联}release(w-data);release(w);return succ; //释放被摘除节点返回接替者
} //release()负责释放复杂结构与算法无直接关系见代码包 时间复杂度O(h)
平衡二叉搜索树
理想平衡树n个节点树高为⌊log_2n⌋的二叉树
适度平衡n个节点树高为渐进O(logn)的二叉树
经过单次修改操作最多只有O(logn)处不再满足适度平衡性条件可在O(logn)时间内使这些不适度平衡处重新适度平衡
AVL树
节点v的平衡因子balFac(v) height(lc(v)) - height(rc(v))
AVL条件AVL树中所有节点满足|balFac(v)| 1 高度为h的AVL树至少含fib(h3)-1个节点进而n个节点的AVL树树高是O(logn)的。 【2012-THU-Fin】将[1481,1992]区间内的整数逐一插入到空AVL树中最后该AVL树的高度是CD A.7 B.8 C.9 D.10 E.以上都不对 共5122^9个元素至少为9。fib(13)-1232也可能是10。 失衡与重平衡
记UT(x)是因对节点x的操作而不满足AVL条件的节点集下假设调整前UT(x)非空
插入失衡
UT(x)中的元素都是x的祖先其不低于x的祖父节点且可能一直失衡到根节点
重平衡自下而上逐个修正 右旋转 左旋转 左-右旋转 右-左旋转 如果节点g的X孩子的Y子树插入导致的失衡 XY在g做X旋转X!Y先在X孩子做X旋转再在g做Y旋转如果插入导致了旋转调整那么本次插入不改变树高
每种旋转都是就地O(1)时间复杂度算法每次将消除一个节点的失衡而AVL树树高是O(logn)的即最多O(logn)次旋转时间复杂度共计O(logn)
删除失衡
UT(x)只有1个节点但可能出现节点的替换自下而上的失衡传播任何进入UT(x)的节点失衡前后高度不变要是失衡了删除部分来自更低的部分但高度取决于更高的子树
删除导致的旋转调整不保证不改变树高树高可能降低
时间复杂度O(logn)
“34”平衡重构 单次重构为就地O(1)时间复杂度算法不计更新高度 【2014-THU-Fin】设在某新节点插入AVL树后尚待平衡化时最低失衡节点为g。若此时g的左、右孩子的平衡因子分别为-1和0则应通过C旋转使之重新恢复平衡。 A.zig B.zigzag C.zagzig D.zag E.不确定 【2016-THU-Fin】若AVL树插入元素的过程中发生了旋转操作则树高必不变。√ 【2016-THU-Fin】如果元素理想随机那么对二叉搜索树做平衡化处理对改进其渐进时间复杂度并没有什么实质的作用。× 伸展树 红黑树 B树
