考研数据结构考点之查找 第七章 查找 7.1 顺序查找7.2 折半查找7.3 分块查找7.4 二叉排序树7.5 平衡二叉树7.6 B树7.7 B+树7.8 散列查找7.9 折半查找、二叉排序树、平衡二叉树对比7.10 T(n)对比分析 7.1 顺序查找 顺序查找又称线性查找 优点：对数据素的存储没有要求，顺序存储或链式存储皆可；对表中记录的有序性也没有要求，无论关键字是否有序，均可应用。 缺点：当n比较大时，平均查找长度较大，效率低 注意！！！对线性的链表只能进行顺序查找算法的时间复杂度计算是通过计算算法的平均查找长度(ASL)得来的，取T(n)=ASL的数量级 ASL又分为查找成功与查找失败两种情况下的ASL. 7.2 折半查找 折半查找又称二分查找。对折半查找而言，画出判定树的结构，知道每个数据素在判定树中的位置。很重要！折半查找的判定树是一颗二叉排序树、也是平衡二叉树平衡二叉树的性质： 右子树节点数-左子树节点数=0或1素个数为n时，判定树高h=log2(n+1)(向上取整，不包括失败结点) 若序列有n个素，则对应判定树有n个圆形的非叶节点，有n+1个叶节点（n个结点的二叉链表有n+1个空链域）只适用于顺序存储，不适合于链式存储算法的时间复杂度计算是通过计算算法的平均查找长度(ASL)得来的，取T(n)=ASL的数量级 ASL又分为查找成功与查找失败两种情况下的ASL. 7.3 分块查找 分块查找一般只考选择题，会手动分析就可以了！ 分块查找又称索引顺序查找，吸取了顺序查找和折半查找各自的优点 特点：块内无序，块间有序 ①索引表可采取顺序查找或折半查找 ②查找表采取顺序查找 当采用折半查找的方式查找索引表时： 若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指的分块中查找若最终的low超出索引表范围，则查找失败注意上述结论是在索引表按照升序排列时得出的 7.4 二叉排序树 二叉排序树又称二叉查找树，是一颗空树或者具有如下性质的非空二叉树： 左子树节点值<根结点值<右子树结点值 二叉排序树的构造： ● 以关键字序列中的第一个素为根节点 ● 按照二叉排序树的插入算法添加结点，新插入的结点一定是根节点 ● 不同的关键字序列可能得到同款二叉排序树 ● 不同的关键字序列也可能得到不同款二叉排序树 7.5 平衡二叉树 平衡二叉树又称为AVL树。简称为平衡树 树上任一结点的左子树和右子树高度之差不超过1 结点的平衡因子=左子树高度-右子树高度 平衡二叉树结点的平衡因子只能为0、1或-1 
7.6 B树 B树也称B-树,它是一棵多路平衡查找树 
注：高度h不包括最后的不带任何信息的叶结点所处的那一层；n指的是关键字个数 性质：最后的不带任何信息的叶结点（代表查找失败的位置）的个数=关键字个数+1； 难点：B树的插入与删除方法，即怎么构造，怎么变动？ 7.7 B+树 与B树明显构造上不同的地方：(注意区分) ● B树中结点的子树个数=结点的关键字个数+1； ● B+树中结点的子树个数=结点的关键字个数； B树与B+树的相同点： 
性质： ● 所有叶结点包含全部关键字及指向相应记录的指针；叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序链接起来。即可以通过下面的指针p将所有的关键字遍历一遍——支持顺序查找 
7.8 散列查找 散列表 根据关键字而直接进行访问的数据结构也就是说，散列表建立了关键字与存储地址之间的一种直接映射关系这种直接的映射关系，就需要一个把关键字映射成该关键字对应地址的函数 上述的这种函数就叫做：散列函数：散列函数是自定义、需要自己设计的；记为Hash(key)=Addr这里的地址Addr可以是数组的下标、索引或内存地址等； 散列函数的构造方法 直接定址法 H(key)=key 或 H(key)=a*key+b; ——适合关键字的分布基本连续的情况，分布不连续，空位太多会造成存储空间的浪费除留取余法 H(key)=key%p; 散列表表长为m，取一个不大于m但最接近或等于m的质数p； 除留取余法的关键是选好p，从而尽可能的减少冲突的可能性数字分析法 取数码分布较为均匀的若干位作为散列地址平方取中法 取关键字的平方值的中间几位作为散列地址 由上述四种构造方法可以看出散列查找是典型的“以空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。 处理冲突的方法 开放定址法 a. 线性探测法 
b. 平方探测法（二次探测法） 可以避免出现“聚集”现象 c. 伪随机序列法拉链法（链接法、链地址法）（Java中的HashMap、HashSet均采用此方法处理冲突） 把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识；拉链法适用于经常进行插入和删除的情况 同义词冲突不等于聚集，故链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象。再散列法 
利用再散列法处理冲突时，按一定的距离，跳跃式地寻找”下一个”空闲位置，减少了发生聚集的可能 “聚集”(“堆积”) 聚集是因选取不当的处理冲突的方法，而导致不同关键字的素对同意散列地址进行争夺的现象。用线性探测法时，容易引发聚集现象。 查找效率 散列查找理想情况下的时间复杂度为O(1)，即与表中素的个数n无关； 散列表的装填因子α，定义为一个表的装满程度；α=表中记录数n/散列表长度m；n也就是关键字个数 散列表的ASL依赖于装填因子α（直接相关），直观地看，α越大，表示装填的记录就越“满”，发生冲突的可能性就越大，ASL也就随之越大； 散列表的查找效率不直接依赖于表中已有表项个数n或表长m。 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子α； 7.9 折半查找、二叉排序树、平衡二叉树对比 ● 折半查找的分析树一定是平衡二叉树，但二叉排序树构造出的树不一定是平衡二叉树 ● 由上可得，折半查找的时间性能有时和二叉排序时相同（当二叉排序树构造出来是平衡二叉树），有时也不同 ● 折半查找适用于顺序存储结构，二叉排序树适用于链式存储结构 ● 当有序表为静态查找表时，采用顺序存储结构，用折半查找 ● 当有序表为动态查找表时，采用链式存储结构（二叉链表），用二叉排序树，插入时采用平衡二叉树的构造方式构造出二叉排序树，时间性能最优，和折半查找相同，优点是在查找过程中实现插入、删除操作方便，只需修改指针即可完成 ● 原树T1,删除关键字v后形成树T2,再将v添加到树T2中形成的T3,当树为二叉排序树与平衡二叉树时的不同 
7.10 T(n)对比分析 
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/37720.html
