查找2008.ppt

第九章 查找 3、分块查找（又称索引查找） 分块查找把线性表分成几块，每一块中元素的顺序是任意的，而块与块之间必须按关键字大小有序。 另需建一索引表，索引表中的一项对应与表中的一块，且索引表的关键字按升序排列。索引表的结构为 例: 欲查找 k=38的结点 9.2 动 态 查 找 树 表 9.2.1 二叉排序树和平衡二叉树 9.2.2 B - 树 和 B+树 9.2.3 键 树 9.2.1 二叉排序树和平衡二叉树 3、如何构造一棵二叉排序树 ——二叉排序树的插入算法 例 {45，24，53，50，12，40，90} 二叉排序树的插入算法 （1）被删除结点是叶子结点 （2）被删除结点只有左子树或只有右子树 （3）被删除的结点既有左子树， 也有右子树 中序序列 CL C …QL Q SL S P PR F 二、平衡二叉树(AVL树) 1.何谓“二叉平衡树”？ 2. 平衡因子 定义为该结点的左子树深度减去右子树深度。 3. 如何构造“二叉平衡树” 方法： 在插入过程中，采用平衡旋转技术 将二叉排序树构造成平衡二叉树的方法 从第一个结点开始构造二叉树 若此二叉树不是平衡二叉树，就进行“旋转”，使之成为平衡二叉树。 加入一个结点，构造二叉排序树。 反复执行 2 , 3直至全部结点组成一棵平衡二叉树为止。 分四种情况讨论： LL型平衡旋转 RR型平衡旋转 LR型平衡旋转 RL型平衡旋转 1. LL型平衡旋转： 由于在A的左子树的左子树中插入新结点，使A的平衡因子由1变为2，只需按图 顺时针旋转。 2. RR型平衡旋转： 由于在A的右子树的右子树中插入新结点，使A的平衡因子由-1变为-2，只需按图 逆时针旋转。 3. LR型平衡旋转： 由于在A的左子树的右子树中插入新结点，使A的平衡因子由1变为2，只需按图先 逆时针旋转，再 顺时针旋转。 4. RL型平衡旋转： 由于在A的右子树的左子树中插入新结点，使A的平衡因子由-1变为-2，只需按图先 顺时针旋转，再 逆时针旋转。 1．定义 B-树是一种平衡的多路查找树，一棵m阶B-树，或为空树，或满足一下性质： 树中每个结点至多有m棵子树; 根结点至少有两棵子树，除非根为树叶； 除根以外的所有非终端结点至少有[m/2]棵子树; 所有非终端结点中包含有下列信息： （n, A0, K1, A1, K2, A2 … Kn, An） 所有叶子结点都出现在同一层次上，且不带信息。 1．定义（续） （n, A0, K1, A1, K2, A2 … Kn, An）中 n为关键字个数。（或n+1为子树的个数） Ki (i=1,2 … n) 为关键字，且 Ki Ki+1 Ai (i=0,1,2 … n) 为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki (i=1,2 … n) ， An所指子树中所有结点的关键字均大于Kn B-树的存储（一棵4阶B-树，其深度为4） 例 查询 47 （1）生成一棵B-树 （2）在已存在的B-树中插入关键字 在一棵3阶B-树中插入关键字（30，26，85，7） Hash表 如果将关键字与存储地址之间建立一个对应的函数关系，以 H(key) 作为关键字为 key 的记录在表中的位置，则查找将直接进行，不必与关键字比较。这种函数称为哈希Hash函数。 用Hash函数建立的表称为Hash表 9.3.2 哈希函数的构造方法 若对于关键字集合中的任一个关键字，经Hash函数映像到地址集合中任何一个地址的概率是相等的，则称此哈希函数为均匀的哈希函数。 亦即， 二. 填装因子a — 标志着Hash表的装满程度 表中填入的记录个数 a= —————————— 哈希表的长度 三、常用的Hash函数构造方法 直接定址法 例 关键字key 0100 1100 1200 1160 key key2 H(key)哈希地址 例：国际标准图书编号 0-442-20586-4 关键字 04 4220 5864 例：国际标准图书编号 0-442-20586-4 关键字 04 4220 5864 例 关键字 28 35 63 77 105 表长=21 H(key) = key mod p p≤m 9.3.3 处理冲突的方法 何为冲突？ 当不同的关键字取相同的Hash函数值时，称为冲突。 1. 开放定址法 H(key) 求得一个地址序列：