四川大学数据结构第8章 查找.pptVIP

数据结构与算法(C++版) 第8章 查找 在每个数据元素中可能存在有若干数据项，可以标识数据元素的数据项称为称为关键字 基于有序顺序表的折半查找 设n个数据元素（或记录）存放在一个有序顺序表中，并按从小到大排好了序 折半查找时, 先求位于查找区间正中的数据元素的下标mid，用其记录的关键字的值与给定值key比较 1. key == elem[mid] 查找成功 2. key elem[mid] 把查找区间缩小到表的前半部分，继续折半查找 3. key elem[mid] 把查找区间缩小到表的后半部分，继续折半查找 如果查找区间已缩小到没有元素（记录），仍未找到想要查找的元素（记录），则查找失败 2. 平衡因子 (balance factor) 每个结点附加一个数字, 给出该结点左子树的高度减去右子树的高度所得的高度差, 这个数字即为结点的平衡因子 AVL树任一结点平衡因子只能取 -1, 0, 1 如果一个结点的平衡因子的绝对值大于1, 则这棵二叉查找树就失去了平衡, 不再是AVL树 如果一棵二叉查找树是平衡的, 且有 n个结点，可证明其高度可保持在O(log2n),平均查找长度也可保持在O(log2n) 3. 平衡化旋转 如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左旋加右旋和右旋加左旋) 1. 平衡二叉树的定义 一棵AVL树或者是空树，或者是具有下列性质的二叉查找树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1 不平衡 平衡 1 2 3 1 2 3 4 5 4 5 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 右单旋转LL型 左单旋转RR型 左右双旋转LR型 右左双旋转RL型 构造二叉平衡（查找）树的方法 在插入过程中，采用平衡旋转技术 依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转 一次 先向右旋转 再向左旋转 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 三、B - 树 B-树是一种 平衡 的 多路 查找 树 1. B-树的概念 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） nm n+1 个指向子树的指针 Ai（0≤i≤n） 多叉树的特性 非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 … Kn Ai-1 所指子树上所有关键字均小于Ki Ai 所指子树上所有关键字均大于Ki 查找树的特性 平衡树的特性 树中所有叶子结点均不带信息，且在树中的同一层次上 根结点或为叶子结点，或至少含有两棵子树 其余所有非叶结点均至少含有?m/2?棵子树，至多含有 m 棵子树 从根结点出发，沿指针查找结点和在结点内进行顺序（或折半）查找 两个过程交叉进行 2. B-树的查找过程 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置 若查找不成功，则返回插入位置 四、B+树 B+每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点 是B-树的一种变型 1. B+树的概念 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 ?m/2?和 m 之间 在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束 若在结点内查找时， Ki-1 ＜给定值≤Ki，则应继续在 Ai 所指子树中进行查找 2. B+树的查找 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root 8.4 散列表 （哈希表） (Hash) 以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系 一、散列表的概念 数据结构与算法(C++版), 清华大学出版社 第*页 * 8.1 查找的基本概念 何谓查找表 ？ 查找表是由同一类型的数据元素(也可称为记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。 所谓查找，就是在数据集合中寻