136 第7 章 集合与搜索 一、复习要点 集合是最基本的抽象数据类型之一。本章讨论了集合的三种存储表示：位数组表示、有序链表表示、并查集。在本章的后半部分，讨论了与集合相关的搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和 AVL 树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n 不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有 n 个对象的二叉搜索树中，搜索效率最高的是高度最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是AVL树。在 AVL 树的讨论中，4 种平衡旋转，选择参加平衡旋转的3 个结点是关键，必须加以注意。 本章复习的要点是： 1 、基本知识点 必须理解集合及其表示方法，包括位数组表示、有序链表表示及其相关操作的实现算法集合及其表示。理解并查集实现的方法。理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握 AVL 树的构造、插入、删除时的调整方法及其性能分析，重点是AVL 树的定义、平衡化旋转、AVL 树的插入和删除、AVL 树的高度。 2 、算法设计 用有序链表表示集合时的求集合的并、交、差的算法 并查集中的构造函数、求根及合并算法 并查集中根据树的高度和根据树中结点个数进行合并的算法 设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法 有序顺序表的顺序搜索算法 有序顺序表的折半搜索的递归算法和非递归算法 二叉搜索树的搜索、插入和删除算法 计算 AVL 树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法 二、难点和重点 1、集合的概念：集合的基本运算、集合的存储表示 用位数组表示集合时集合基本运算的实现 用有序链表表示集合时集合基本运算的实现 2、 并查集：并查集定义、并查集的三种基本运算的实现 3、基本搜索方法 对一般表的顺序搜索算法(包括有监视哨和没有监视哨) 对有序顺序表的顺序搜索算法，包括递归和非...
