山东理工大学理学院数据结构课件 第九章.pptVIP

3．二叉排序树的插入 根据动态查找表的定义，“插入”操作在查找不成功时才进行; 二、二叉平衡树 1. 二叉平衡树定义 1. 二叉平衡树定义 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root B+树 2．查找过程 1).在 B+ 树上，既可以进行缩小范围的 查找，也可以进行顺序查找； 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root B+树 2).在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； 3).若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找； 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root B+树 3．插入 操作 1). 插入仅在叶子结点进行； 2). 当叶子结点的关键字个数大于m时，要分裂成 两个关键字个数分别为└ (m＋1)/2┘和 ?(m＋1)/2?的结点，且它们的双亲同时包含这 两个结点中的最大值； 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root B+树 4．删除操作 1). 删除仅在叶子结点； 2). 叶子结点的最大关键字被删除，非终端结点 中的值仍然可以作为“分解关键字”存在； 3). 关键字个数少于?m/2?时，需要合并； 9.2 静态查找表 9.3 动态查找树表 9.4 哈希表 9.1 基本概念 第九章 查找表 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 9.3 哈 希 表 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 一、哈希表是什么？ 查找的过程为给定值依次和关键字集合中各个关键字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。 准 考 证 号 姓名 各科成绩 总分 政治 语文 外语 数学 物理 化学 生物 . . . 179321 179322 179333 . . 145321 . . . 陈红 陆华 张平. . . 张平 . . . 84 76 85 . . . 76 . . . 76 84 88 . . 64. . . . 74 65 73. . . 75 . . . 93 87 79 . . . 88 . . . 87 69 62 . . . 66 . . . 76 57 63 . . . 67 . . . 87 71 78 . .. 81 . . . 63 54 55 . . 73 准 考 证 号 姓名 政治 语文 外语 数学 物理 化学 生物 总分 物理地址 8010 8230 8240 8250 8700 关键字 存放位置 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 只有一个办法：预先知道所查关键字在表中的物理存储位置， 对于频繁使用的查找表， 希望 ASL = 0。 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 哈希查找的基本思想： 以查找表中的每个元素的关键字key为自变量，通过函数H(key)计算出函数值，把这个值解释为存储空间的单元地址，并将该元素存储到这个地址单元中。这种函数H(key)就称为哈希函数。 在哈希表上进行查找时，首先根据给定值的关键字key，用哈希函数H(key)计算出存储地址，然后按此地址取出对应的元素。 如果以学号的后三位000 ~ 999作为每个元素存储单元地址建立顺序查找表。 例如：某校为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前