数据结构与算法第七章 搜索结构
有序顺序表的折半搜索判定树与\(ASL_{suc},ASL_{unsuc}\)的计算
\(\displaystyle ASL_{suc}=\frac{到达每个结点比较总次数}{结点个数}\)
\(\displaystyle ASL_{unsuc}=\frac{到达空段的比较总次数}{空段总数(节点个数+1)}\)
二叉搜索树：
将二叉搜索树转为顺序序列，使用中序遍历。
二叉搜索树的建立（代码与手绘流程图）：
二叉搜索树的搜索、插入与删除：
插入：先检查此元素是否已经存在（如果允许重复出现则另当别论），如果需要插入，在逐次向下搜索时，若找到叶节点，则与之比较，根据结果将新数插入到其左/右孩子处。
删除：被删节点是叶节点，将此指针置为空再释放即可
如果是非叶节点，则在删除后需要连接断开的二叉树。被删结点右子树为空，使用左子女顶替其位置。被删结点左子树为空，使用右子女顶替其位置。
被删结点左右子树均不为空，取其右子树中序遍历下第一个节点（关键码在右子树中最小），用其顶替，再处理此结点删除问题（此时转为被删结点左子树为空情况）；或取其左子树中序遍历最后一个节点（关键码在左子树中最大），用其顶替，再处理此结点删除问题（此时转为被删结点右子树为空情况）
插入一个元素，再删除之，前后两种树不一定相同。
如果此元素不存在于树中，是相同的；如果存在于树中，则不一定相同（如果删除的不是叶结点）。
AVL树
具有下列性质的二叉搜索树：其左子树，右子树均为AVL树，左右子树高度之差绝对值不超过1。
BF：节点平衡因子：即该节点右子树与左子树的高度差，取值只能为-1，0，1，否则失去平衡，如果均能保持，则树高可以保持在\(O(\log_2n)\)，平均搜索长度也可保持在\(O(\log_2n)\)
平衡化旋转：
插入新结点时，如果在某结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
AVL树的插入：设新结点的父节点平衡因子为bf
bf为0时，无需平衡化处理
bf为1，-1时，需要向上回溯检查是否出现失衡状态
bf为2时，若其右子女bf为1，执行左单旋转，若为-1，执行先右后左双旋转
bf为-2时，若其左子女bf为-1，执行右单旋转，若为1，执行先左后右双旋转
AVL树的删除：同二叉搜索树删除，需反向追踪高度变化
用shorter指明子树高度是否被缩短。每个结点上的操作取决于shorter和bf，有时要依赖子女bf。shorter初始True。
对从x双亲到根的路径上各结点p，在shorter为True时执行下面操作。如果shorter变False，算法终止。
当前结点p的bf为0。如果它的左子树/右子树被缩短，bf改为1/-1，shorter置False。
p的bf不为0且较高子树被缩短。则p的bf置0，置shorter为True。
p的bf不为0，且较矮子树被缩短。则p不平衡。令p较高子树根为q（该子树未被缩短），根据q的bf，有如下3种平衡化操作。旋转的方向取决结点p的哪一棵子树被缩短。
1）q（较高的子树）的bf为0，执行一个单旋转恢复p平衡，置shorter为False。无需检查上层结点bf。
2）q的bf与p的bf相同，执行一个单旋转恢复平衡，p和q的bf均置0，置shorter为True。继续检查上层结点bf。
3）p与q的bf相反，执行一个双旋转恢复平衡。先绕q转再绕p转。新根bf置0，其他结点bf相应处理，置shorter为True。
AVL树插入时间取决于树高。记\(N_h\)是高度为\(h\)的AVL树的最小节点数，根的两棵子树高度分别为\(h-1,h-2\)，子树满足AVL树定义，有：
可得\(N_h+1=(N_{h-1}+1)+(N_{h-2}+1)\),记\(N_h+1=f_h,f_h=f_{h-1}+f_{h-2},f_h=fibonacci_{h+2}\);
\(\displaystyle fibonacci_h \approx (\frac{1+\sqrt{5}}{2})^h/\sqrt{5}\)
\(\displaystyle N_h\approx (\frac{1+\sqrt{5}}{2})^{h+2}/\sqrt{5}-1\)
有\(n\)个结点的AVL树高度不超过\(O(\log_2n)\)，故删除节点并做平衡化旋转/插入数据时间为\(O(\log_2n)\)
二叉搜索树适合较小数据规模，一般使用B树，B+树。