查找课件.ppt

索引部分 3 阶B+树 (p246) B+树 —— B-树的一种变型树。 m 阶B+树与 m 阶B-树的差异： 有n 棵子树的结点中含有n 个关键字; 所有叶子结点中包含了全部关键字和指向其相应记录的指针；并且，所有叶子结点按关键字从小到大依次链接构成一个有序链表； 所有的非终端结点可以看成是索引部分,每个非终端结点中含有其子树中的最大关键字和指向其子树根结点的指针。 m 阶B+树与m 阶B-树的共同点： 每个结点至多有m 棵子树； 若根不是叶子结点, 则至少有两棵子树; 除根之外的每个非终端结点至少有?m/2? 棵子树； 所有的叶子结点都在同一层。 例: 3 阶B+树 查找关键字为59 的记录； 查找关键字大于或等于37 的记录； 顺序查找全部记录。 B+树的查找 在B+ 树上，既可以按关键字进行随机查找，也可以进行顺序查找； 在B+ 树上进行随机查找时，不论查找成功与否，都必须查到叶子结点才能结束。 B+树查找小结 B+树的插入和删除 B+树的插入在叶子结点中进行, 当结点中的关键字个数大于m 时需分裂成两个结点, 它们所含关键字的个数分别为 ?(m+1)/2? 和 ?(m+1)/2?。并且, 他们的双亲结点中应同时包含这两个结点中的最大关键字。 B+树的删除也需在叶子结点中进行，若因删除而使结点中的关键字个数少于?m/2?，其处理过程和B-树类似。 3 阶B+树 B+树的插入和删除 当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。 9.3 哈希表 查找操作建立在比较的基础之上，查找的效率依赖于查找过程中进行的比较次数，平均查找长度总是查找表中记录个数 n 的函数。 9.3.1 什么是哈希表 前面讨论的查找表的各种表示方法和查找技术具有以下共同特点： 记录在表中的位置和其关键字之间不存在一种确定的关系。 可能的办法是：预先知道所查关键字在表中的位置。 即要求：在关键字与记录在表中的存储位置之间建立一个确定的函数关系。 根据上述思路，一种存储和查找方法应运而生—— 哈希法( hashing 散列法、杂凑法) 对于频繁使用的查找表，希望 ASL = O(1) 例如：为每年招收的n≤1000 名新生建立一个查找表，关键字为学号，其取值范围是 xx000 ~ xx999 (前两位为年份)。 若以下标为000 ~ 999的顺序表表示之, 则查找过程可以简单进行：取给定学号的后三位作地址，不需要经过比较便可直接从顺序表中找到待查关键字。 设R为查找表中任一记录，其关键字为 key，R的存储位置通过下式计算： Loc(R) = f (key) 其中 f (key) 为一个确定的函数, 称为哈希函数，其函数值 Loc(R) 称为哈希地址。 哈希函数( Hash function 散列函数 ) ( Zhao, Qian, Sun, Li, Wu, Chen, Han, Ding, An ) 例：对于下列 9 个关键字 f (key) = ?( key[0] - A + 1 ) /2? Chen Zhao Qian Sun Li Wu Han An Ding 问题: 若添加关键字 Zhou , 怎么办？ 能否找到一个不发生地址冲突的哈希函数？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 key 的第一个字母在字母表中的序号 从以上例子可见， 哈希函数是一个映象，它将一个关键字集合映射到某个地址集合上。 通常, 哈希函数是一个压缩映象。因此,很容易发生冲突现象，即： key1? key2，而 f (key1) = f (key2)。 * 具有相同哈希函数值的关键字称作同义词。 哈希函数是从关键字集合K 到地址集合L 的一个映象 f : K?L; K L f f 的定义域 f 的作用域 f 的值域 ? L 冲突 压缩映象 Status Delete( BiTree p ) { // 从二叉排序树中删除结点*p if (!p-rchild) { // 右子树空则只需重接其左子树 q = p; p = p-lchild; free(q); } else if (!p-lchild) { // 只需重接其右子树 q = p; p = p-rchild; free(q); } else // 左右子树均不空，采用删除方案二 算法9.8 (p230~231) { q = p; s = p-lchild; while