搜索结构

• 实施搜索时有两种不同的环境。
• 静态环境，搜索结构在插入和删除等操作的前后不发生改变。
• 动态环境，为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。

静态搜索结构

• 在静态搜索表中，数据元素存放于数组中，利用数组元素的下标作为数据元素的存放地址。搜索算法根据给定值 k，在数组中进行搜索。直到找到 k 在数组中的存放位置或可确定在数组中找不到 k 为止。

• 数据表与搜索表的类定义
代码

• 顺序搜索（Sequential Search）
• 一般的顺序搜索算法在第二章已经讨论过，本章介绍一种使用“监视哨”的顺序搜索方法。
• 设在数据表 dataList 中顺序搜索关键码与 给定值 x 相等的数据元素，要求数据元素在表中从下标 0 开始存放, 下标为 CurrentSize 的元素作为控制搜索过程自动结束的“监视哨”使用。
• 若搜索成功，则函数返回该元素在表中序号 Location（比下标大 1）, 若搜索失败，则函数返回 CurrentSize+1。
• 顺序搜索的递归算法
• 采用递归方法搜索值为 x 的元素，每递归一层就向待查元素逼近一个位置，直到到达该元素。假设待查元素在第 i（1≤i≤n）个位置，则算法递归深度达 i（1～i）。
• 二分查找
• 设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序。
• 折半搜索时, 先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较
• 如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。

二叉搜索树

• 二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
• 每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。
• 左子树（如果非空）上所有结点的关键码都小于根结点的关键码。
• 右子树（如果非空）上所有结点的关键码都大于根结点的关键码。
• 左子树和右子树也是二叉搜索树。

• 如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。

• 二叉树的搜索应该是递归的，从根结点开始，如果搜索值小于当前节点，就递归到左子树，否则到右子树
设树的高度为h，最多比较次数不超过h。

• 二叉搜索树的插入算法
• 为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。
• 如果搜索成功，说明树中已经有这个元素，不再插入；
• 如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。

• 二叉搜索树的删除算法
• 在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。
• 为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。
• 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。
• 被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。
• 被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。
• 被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。

AVL树--- 高度平衡的二叉搜索树

• AVL 树的定义：一棵 AVL 树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是 AVL 树，且左子树和右子树的高度之差的绝对值不超过1。

• 结点的平衡因子bf (balance factor)
• 每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差，这个数字即为结点的平衡因子bf。
• AVL树任一结点的平衡因子只能取 -1, 0, 1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树。
• 如果一棵有 n 个结点的二叉搜索树是高度平衡的，其高度可保持在O(log2n)，平均搜索长度也可保持在O(log2n)。

• AVL树的平衡化旋转
• 如果在一棵平衡的二叉搜索树中插入一个新结点或者删除一个结点后，造成了不平衡。必须调整树的结构，使之平衡化。
• 平衡化旋转有两类：
• 单旋转 (左单旋转和右单旋转)
• 双旋转 (先左后右和先右后左)

• 左单旋转

• 右单旋转

 

• 先左后右双旋转 (RotationLeftRight)

• 先右后左双旋转 (RotationRightLeft)

• AVL树的插入
• 在插入新结点后，需从插入结点沿通向根的路径向上回溯。
• 如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
• 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转。
• 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
• 新结点p的平衡因子为0。设其父结点为pr，若p是pr的右子女，则pr的平衡因子增加1，否则，pr的平衡因子减小1。插入新结点并修改pr的平衡因子值后，pr的平衡因子值有三种情况：
1. 结点pr的平衡因子为0。说明刚才是在pr的较矮的子树上插入了新结点，此时不需做平衡化处理，返回主程序。子树的高度不变。

2. 结点pr的平衡因子的绝对值|bf| = 1。说明插入前pr的平衡因子是0，插入新结点后，以pr为根的子树不需平衡化旋转。但该子树高度增加，还需从结点pr向根方向回溯，继续考查结点pr双亲(pr = Parent(pr))的平衡状态。
3. 结点pr的平衡因子的绝对值|bf| = 2。说明新结点在较高的子树上插入，造成了不平衡，需要做平衡化旋转。此时可进一步分2种情况讨论
1. 若结点pr的bf = 2，说明右子树高，结合其右子女q 的bf分别处理：
1. 若q的bf为1，执行左单旋转。
2. 若q的bf为-1，执行先右后左双旋转。

2. 若结点pr的bf = -2，说明左子树高，结合其左子女q 的bf分别处理：
1. 若q的bf为-1，执行右单旋转；
2. 若q的bf为1，执行先左后右双旋转。

• AVL树的删除
• 如果被删结点x最多只有一个子女，可做简单删除:
• 将结点x从树中删去。
• 如果结点x有一个子女，可以简单地把x的双亲中原来指向x的指针改成指到这个子女结点；
• 如果结点x没有子女，x双亲原来指向x的指针置为NULL。
• 将原来以结点x的父结点为根的子树的高度减1。
• 如果被删结点 x 有两个子女:
• 搜索x在中序次序下的直接前驱 y (同样也可以找直接后继)。
• 把结点 y 的内容传送给结点 x，现在问题转移到删除结点 y，把结点 y 当作被删结点。
• 因为结点 y 最多有一个子女，可以简单地用 1. 给出的方法进行删除。
• 删除完x后，必须沿结点x的父结点通向根的路径反向追踪高度的变化对路径上各个结点的影响。
• 用一个布尔变量shorter（缩短）来指明子树高度是否被缩短。在每个结点上要做的操作取决于shorter的值和结点的bf，有时还要依赖子女的bf。
• 布尔变量shorter的值初始化为True。然后对于从x的双亲到根的路径上的各个结点p ，如果shorter变成False，算法终止；在 shorter保持为True时执行下面的操作：
1. 当前结点 p 的bf为0。如果它的左子树或右子树被缩短，则它的bf改为1或-1，同时 shorter置为False。不需要继续检查上层结点的平衡因子

2. 结点 p 的 bf 不为0且较高的子树被缩短。则 p 的 bf 改为0，同时shorter置为True。还要继续检查上层结点的平衡因子。

3. 结点 p 的 bf 不为0，且较矮的子树又被缩短。则在结点 p 发生不平衡。需要进行平衡化旋转来恢复平衡。令 p 的较高的子树的根为 q（该子树未被缩短），根据 q 的 bf，有如下 3 种平衡化操作：
1. 如果 q（较高的子树）的 bf 为0，执行一个单旋转来恢复结点 p 的平衡，置shorter为False。无需检查上层结点的平衡因子。
2. 如果 q 的 bf 与 p 的 bf 相同，则执行一个单旋转来恢复平衡，结点 p 和 q 的 bf 均改为0，同时置shorter为True。还要继续检查上层结点的平衡因子。
3. 如果 p 与 q 的 bf 相反，则执行一个双旋转来恢复平衡。新根结点的 bf 置为0，其他结点的 bf 相应处理，同时置shorter为True。还要继续检查上层结点的平衡因子。

• AVL树的性能分析
• 设 Nh 是高度为 h 的AVL树的最小结点数。最差情况下，根的一棵子树的高度为，另一棵子树的高度为，这两棵子树也是高度平衡的。因此有 (空树) (仅有根结点) （类似斐波那契数列, F0 = 0, F1 = 1, Fh = Fh-1 + Fh-2 ）
• 可以证明, 对于 , 有 成立。
• 由此可以推出，有 n 个结点的AVL树的高度不超过因此，在AVL树中，搜索、插入、删除一个结点并做平衡化旋转所需时间为 O(log2n)。