《《二分查找及算法设计》-公开课件PPT》由会员分享，可在线阅读，更多相关《《二分查找及算法设计》-公开课件PPT（22页珍藏版）》请在金锄头文库上搜索。
1、8查找 二分查找及算法设计二叉排序树及构造平衡二叉树的查找 插入及旋转hash表的构造及查找 8 1二分 折半 查找 一 二分查找的先决条件表中结点按关键字有序 且顺序 一维数组 存储 二 二分法思想 取中 比较 1 求有序表的中间位置mid 2 若r mid key k 查找成功 若r mid key k 在左子表中继续进行二分查找 若r mid key k 则在右子表中继续进行二分查找 12 21 30 35 38 40 48 55 56 60 64 1234567891011 i 1 j 11 二分法查找示例 1 k 35 K r m 在左半部分继续查找 m i j 2 6 i 1 j
2、m 1 5 m i j 2 3 K r m 在右半部分继续查找 i m 1 4 j 5 m i j 2 4 r m k 查找成功 m i j 2 6 12 21 30 35 38 40 48 55 56 60 64 i 1 j 11 m i j 2 6 r m k 在左半部分继续查找 i 7 j m 1 8 m i j 2 7 r m k 在左半部分继续查找 i 8 j m 1 7 i j 查找失败 二分法查找示例 2 k 50 1234567891011 三 存储结构keyinfotypedefstruct keytypekey elemtype k1 k2 k3 kn 0123n 四 算法
3、描述 intSearch bin elemtyper intn keytypek r 1 r n 是按key排序的n个元素 在表中查找ki 1 j n while i j mid i j 2 取中if k r mid key return mid 查找成功elseif k r mid key j mid 1 在左半部分继续查找elsei mid 1 在右半部分继续查找 return 0 k不在该有序表中 r j key k r i key 五 二分查找判定树 以11个结点为例 12 21 30 35 38 40 48 55 56 60 64 1234567891011 平均查找长度ASL 1
4、2 2 4 3 4 4 11 3二分查找算法的时间复杂度T n O log2n 45 53 100 61 12 3 90 78 37 24 8 2二叉排序树 一 二叉排序树的定义二叉排序树或空 或对于二叉树中的每一个结点 若它的左子树非空 则左子树上所有结点的关键字值均小于该结点的值 若根的右子树非空 则右子树上的所有结点的关键字值均大于该结点的值 二 二叉排序树的特点中序遍历得一有 升 序序列 查找方法 若根结点的关键字值等于查找的关键字 查找成功 否则 若小于根结点的关键字值 查其左子树 若大于根结点的关键字的值 则查其右子树 在左右子树上的操作类似 45 53 100 61 12 3 9
5、0 78 37 24 三 二叉排序树的查找 例8 1 查找k 24 45 53 100 61 12 3 90 78 37 24 四 二叉排序树的插入 若二叉树为空 则生成根结点 若二叉树非空 1 首先进行查找 找出被插结点的父结点 2 判断被插结点是其父结点的左 右儿子 将其作为叶子结点插入 60 例8 2 在二叉排序树中插入60 45 53 100 61 12 3 90 78 37 24 五 二叉排序树的构造 若二叉树为空 则生成根结点 若二叉树非空 1 首先执行查找 找到被插结点的父亲结点 2 判断被插结点是其父亲结点的左 右儿子 将其结点插入 例8 3 以 45 53 12 37 24
6、100 3 61 90 78 构造二叉排序树 53 93 37 24 45 12 一 什么是平衡二叉树或空树 或是具有下列性质的二叉排序树 它的左子树和右子树都是平衡二叉树 且左子树和右子树的深度之差的绝对值不超过1 平衡二叉树 AVL树 二 平衡因子 BalanceFactor 左子树的深度 右子树的深度即平衡二叉树中每一结点的平衡因子为 0 1 1 0 1 0 0 0 0 三 平衡二叉树的查找 即二叉排序树查找 45 90 100 78 12 3 61 37 24 0 1 0 0 0 0 1 1 1 插入15 45 90 100 78 12 3 61 37 24 0 1 0 0 0 1 1
7、 2 0 15 2 1 找插入位置 2 插入结点 3 若插入后导致不平衡 则进行调整 四 平衡的二叉树的插入 45 90 100 78 12 3 61 37 24 0 1 0 0 1 1 0 LL旋转 45 90 100 78 12 3 61 24 37 0 1 0 0 0 0 1 2 0 50 0 15 2 0 15 0 0 1 找插入位置 2 插入结点 3 若插入后导致不平衡 则进行调整 四 平衡的二叉树的插入 一 hash函数 hash表设计1个hash函数 计算Hash函数 其函数值恰好是key在hash表中的地址hash key i 0 m 1 二 hash查找的特点 基于计算 8
8、4hash 散列 查找 例8 3hash查找示例 人口统计表 在右表中查找1989年出生的人数 查找方法 1 顺序查找查找方法 2 二分查找查找方法 3 hash查找hash key key 1949 1989 1949 40 除留余数法hash key key pp m 表长 关键问题是 如何选取p p应为不大于m的最大质数例 设表长m 8 16 32 64 128 1001则p 7 13 31 61 127 1001 三 hash函数的构造方法 若对于不同的键值k1和k2 且k1 k2 但hash k1 hash k2 即具有相同的散列地址 这种现象称为冲突 称k1 k2称为同义词 例8
9、4key 3 15 20 24 m 5 表长 hash k k 5hash 15 0hash 20 0产生冲突 四 冲突的概念与处理方法 冲突的处理 链地址法 将具有相同散列地址的记录都存储在同一个线性链表中 例8 5key 14 1 68 27 55 23 11 10 19 20 79 84 hash key key 13 用链地址法解决冲突 构造hash表 hash 14 hash 1 hash 27 hash 79 1hash 68 hash 55 3hash 19 hash 84 6hash 20 7hash 23 hash 10 10hash 11 11 1 27 79 hash k
10、ey key 13hash 14 1hash 1 1hash 68 3hash 27 1hash 55 3hash 23 10hash 11 11hash 10 10hash 19 6hash 20 7hash 79 1hash 84 6 14 68 19 20 23 11 55 84 10 ASL 6 1 4 2 1 3 1 4 12 21 12 对给定的关键值key 若地址d 即hash key d 的单元发生冲突 则依次探查下述地址单元 d 1 d 2 m 1 0 1 d 1直到找到一个开放的地址 空位置 止 将发生冲突的键值放到该地址中 设增量函数为d i 1 2 3 m 1 m表长i 为探测次数 冲突的处理 线性探测法 例8 6以 14 1 68 27 55 23 11 10 19 20 79 84 构造hash表 hash表长度为17 hash key key 17 用线性探测法解决冲突 hash表 012345678910111213141516 14 68 1 55 27 20 19 84 79 11 23 10 比较次数 33ASL 1 10 3 2 12 16 12
