【数据结构笔记】搜索树

二叉搜索树

任一节点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(h+3)-1个节点，进而n个节点的AVL树树高是O(logn)的。

【2012-THU-Fin】将[1481,1992]区间内的整数逐一插入到空AVL树中，最后该AVL树的高度是（CD）
A.7 
B.8 
C.9 
D.10 
E.以上都不对
共512=2^9个元素，至少为9。fib(13)-1=232，也可能是10。

失衡与重平衡

记UT(x)是因对节点x的操作而不满足AVL条件的节点集，下假设调整前UT(x)非空

插入失衡

UT(x)中的元素都是x的祖先，其不低于x的祖父节点，且可能一直失衡到根节点

重平衡自下而上逐个修正

右旋转

左旋转

左-右旋转

右-左旋转

• 如果节点g的X孩子的Y子树插入导致的失衡
  • X=Y，在g做X旋转
  • X!=Y，先在X孩子做X旋转，再在g做Y旋转
• 如果插入导致了旋转调整，那么本次插入不改变树高

每种旋转都是就地O(1)时间复杂度算法，每次将消除一个节点的失衡，而AVL树树高是O(logn)的，即最多O(logn)次旋转，时间复杂度共计O(logn)

删除失衡

UT(x)只有1个节点，但可能出现节点的替换（自下而上的失衡传播）；任何进入UT(x)的节点失衡前后高度不变（要是失衡了，删除部分来自更低的部分，但高度取决于更高的子树）

删除导致的旋转调整不保证不改变树高，树高可能降低

时间复杂度O(logn)

“3+4”平衡重构

单次重构为就地O(1)时间复杂度算法（不计更新高度）

【2014-THU-Fin】设在某新节点插入AVL树后（尚待平衡化时），最低失衡节点为g。若此时g的左、右孩子的平衡因子分别为-1和0，则应通过（C）旋转使之重新恢复平衡。 
A.zig 
B.zig+zag 
C.zag+zig 
D.zag 
E.不确定 

【2016-THU-Fin】若AVL树插入元素的过程中发生了旋转操作，则树高必不变。（√）

【2016-THU-Fin】如果元素理想随机，那么对二叉搜索树做平衡化处理，对改进其渐进时间复杂度并没有什么实质的作用。（×）

伸展树

红黑树

B树