当前位置：首页 > news >正文

检察网站建设医院网站整站源码

news 2025/9/17 11:40:32

检察网站建设,医院网站整站源码,网络舆情监测与研判,云龙主机 wordpress二叉搜索树任一节点x的左/右子树中，所有非空节点均不大于（不小于）x 必须是所有的非空节点，仅左右孩子不够（左孩子的右孩子可能很大）一棵二叉树是二叉搜索树当且仅当中序遍历序列是单调非降序列两棵二叉…

二叉搜索树

任一节点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)