1. 激活谷首页
  2. 激活谷笔记

二叉排序树查找算法的优缺点_二叉排序树的查找效率

• 激活谷笔记

二叉排序树查找算法的优缺点_二叉排序树的查找效率【ALG 算法】022 | 顺序查找、二分查找[69] 查找基本概念查找 ：在数据集合中寻找满⾜某种条件的数据素的过程称为查找。查找表（查找结构）：⽤于查找的数据集合称为查找表，它由同⼀类型的数据素（或记录）组成关键字 key：数据素中唯⼀标识该素

【ALG 算法】022 | 顺序查找、二分查找 　　[69] 查找基本概念 　　查找 ：在数据集合中寻找满⾜某种条件的数据素的过程称为查找。查找表（查找结构）：⽤于查找的数据集合称为查找表，它由同⼀类型的数据素（或记录）组成关键字 key：数据素中唯⼀标识该素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。 　　例如：在信息表中，姓名无法作为关键字，但是身份证号可以（唯一性） 　　1.对查找表的常见操作 　　查找符合条件的数据素； 静态查找表，仅查找速度即可。插⼊、删除某个数据素；动态查找表，除了查找速度，也要插/删操作是否⽅便实现。 　　2.查找算法的评价指标 　　查找长度： 在查找运算中，需要对⽐关键字的次数称为查找⻓度。平均查找⻓度（ASL, Average Search Length）： 所有查找过程中进⾏关键字的⽐较次数的平均值： 　　
ASL = \sum_{i=1}^n P_i C_i 　　其中，代表数据素个数，
P_i 代表第个素的概率，
C_i 代表第个素的查找长度。通常认为查找任何⼀个素的概率都相同。 在二叉搜索树（BST）中曾经提及
ASL 的计算，以左边的二叉树为例： 查找成功，共有8种可能性（8个结点） 第一层的查找次数为1，第二层的查找次数为2（必须先与50对比，发现不是50，才可能到第二层），同理，第三层查找次数为3，第4层查找次数为4。 　　总平均查找长度：
ASL = (1 × 1 + 2 × 2 + 3 × 4 + 4 × 1)/8 = 2.62
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二叉排序树查找成功ASL查找失败，共有9种可能性，因为有8个结点划分了9个区间段，落在任意一个区间段的概率时相等的。 除了60 ~ 68，68 ~ 70 这两个区间段（不包含边界值）需要四次查找外，其均需要三次查找。 　　因此，总平均查找长度：
ASL = (3 × 7 + 4 × 2)/9 = 3.22
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二叉排序树查找失败ASL 　　右侧二叉树的平均查找长度也同理可以计算。
ASL 的数量级反应了查找算法时间复杂度。评价⼀个查找算法的效率时，通常考虑查找成功、查找失败两种情况的
ASL 。 　　[70] 顺序查找 　　1.顺序查找的算法思想 　　顺序查找，⼜叫“线性查找”，通常⽤于线性表。算法思想：从头到脚挨个找（或者反过来也OK）。 　　查找实现 　　例如以线性表为例， 　　
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率顺序查找 　　哨兵模式 　　也可以用“哨兵”方法来实现顺序查找 ： 　　使用0号位置存储“哨兵”，即要查找的素，后尾向头部依次遍历搜索。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率顺序查找成功 哨兵模式
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率顺序查找失败 哨兵模式 　　如果成功，则返回序数，失败则返回0。优点：⽆需判断是否越界（最终一定会结束循环），效率更⾼（但是也高不了多少，因为阶数一样）。 　　查找效率分析 　　查找成功，每一个素查找的可能性均等：
{ASL}_{s} = \frac{1 + 2 + 3 + . . . + n}{n} = \frac {n + 1}{2} 　　因为查找素为n个，每个查找素的概率均等，都是
\frac{1}{n} ，其总期望见上。
{ASL}_{f} = n + 1 总体时间复杂度:
O(N) 。 　　2. 顺序查找的优化（对有序表） 　　如果原顺序表，本来就是有顺序的（递增或者递减排序），在查找到某个素（大于或者小于）要寻找的值的时候，对后续的素就不需要再进行判定了。原有对顺序表的判定将转化成为“判定树”结构。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率查找判定树 　　⼀个成功结点的查找⻓度 = ⾃身所在层数，⼀个失败结点的查找⻓度 = 其⽗节点所在层数默认情况下，各种失败情况或成功情况都等概率发⽣。由n个结点划分出共有n+1种查找失败的情况。上图中，方形是失败结点，圆形是成功结点。 查找成功：
{ASL}_{s} = \frac{1 + 2 + 3 + . . . + n}{n} = \frac {n + 1}{2} 查找失败：
{ASL}_{f} = \frac{1 + 2 + 3 + . . . + n + n}{n+1} = \frac {n}{2} + \frac {n}{n + 1} 对比之前的查找效率，查找成功长度不变，但是查找失败长度缩减近一半。 　　3. 顺序查找的优化（被查概率不相等） 　　对于被查概率不相等时，被查概率⼤的放在靠前位置s，这样查找成功时候
ASL 更少。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率 概率不同的查找 　　[71] 折半查找 　　1.查找过程推演 　　折半查找，⼜称“⼆分查找”，仅适⽤于有序、具有随机存取的顺序表。链表不具备随机存取的特点，不适用于二分查找。【问题】在数组 顺序表中查找33，并返回其位序。 起始状态，、分别指向头位序、尾位序的素，mid 指向中间素，开始查找。 对比target和mid所指素的值，发现，锁定目标一定位于右半边。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找1low移至mid的下一位，mid更新。对比target和mid所指素的值，发现，锁定目标一定位于左半边。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找2high移动至mid的前一位，mid更新。对比target和mid所指素的值，发现，锁定目标一定位于右半边。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找3low移至mid的下一位，mid更新。对比target和mid所指素的值，发现，查找成功。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找4 　　查找失败的例子暂时省略，依照查找成功可以推演。 算法程序实现： 　　注意，在查找失败的时候，、指针均在的基础上加1或者减1，因为在上一轮的判定过程中，已经排除mid位置与target不符合，所以，可以直接跳过该序列。另外，如果顺序表时降序排列，代码的逻辑需要重新修改。 　　2.查找效率分析，使用判定树 　　以上查找分析查找过程，画查找判定树： – 查找成功判定树：
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找成功判定树 　　
{ASL}_{s} = \frac{1 + 2 × 2 + 3 × 4 + 4 × 4}{11} = 3 查找失败判定树：
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率二分查找失败判定树 　　
{ASL}_{f} = \frac{3 × 4 + 4 × 8}{12} = 3.67 　　3. 查找判定树的构造 　　如果当前，和之间有奇数个素，则 分隔后，左右两部分素个数相等（根节点占据一个）。如果当前，和之间有偶数个素，则 分隔后，左半部分比右半部分少⼀个素（由于根节点mid向下取整）。
二叉排序树查找算法的优缺点_二叉排序树的查找效率
二叉排序树查找算法的优缺点_二叉排序树的查找效率判定树构造 　　因此，折半查找的判定树中，若
mid = ⌊(low + high) / 2 ⌋ ，则对于任何⼀个结点，必有： 右子树结点数 – 左子树结点数 =0 或 1 　　所以，根据平衡二叉树（AVL）定义，折半查找的判定树⼀定是平衡⼆叉树。在折半查找的判定树中，只有最下⾯⼀层是不满的。树高：
h = ⌈\log_2{(N + 1)}⌉ 这里的树⾼不包含含失败结点。 　　判定树结点关键字：左 < 中 < 右，同时，满⾜⼆叉排序树（BST）的定义。 所以，二分查找是综合了二叉排序树和平衡二叉树的一种算法。 　　4. 查找效率分析 　　N个结点，将区间段划分成N + 1个，因此失败结点：N +1 个，等于成功结点的空链域数量。在判定树的前提下，查找成功的
ASL_s ≤ h , 查找失败的
ASL_f ≤ h 。因此，折半查找的时间复杂度为
O(\log_2{N}) 。

2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/89615.html

赞 (0)
0
上一篇 2024年 6月 21日 上午11:28
下一篇 2024年 6月 21日 上午11:36

相关推荐

关注微信