[工学]数据结构第17次课-查找C.ppt

8.2 静态查找表 一、顺序查找（ Linear search，又称线性查找 ） 二、折半查找（又称二分查找或对分查找） 四、分块查找（索引顺序查找） 查找步骤分两步进行： 8.3 动态查找表 1、二叉排序树的定义回顾 2、二叉排序树的插入与删除 讨论1：二叉排序树的插入和查找操作 讨论2：二叉排序树的删除操作 3.二叉排序树的查找分析 最好情况：即：与折半查找中的判定树相同（形态比较均衡） 二 平衡二叉树( AVL树） 什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树并且 左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF (Balance Factor)是 左子树的深度减去右子树的深度,它只可能是 -1, 0, 1 平衡二叉树(也称AVL树)的深度为O(log2N) (其中N为结点个数) 它的平均查找长度也是O(log2N) 平衡二叉树及平衡因子举例 不平衡二叉树及平衡因子举例 二叉排序树转成平衡树失去平衡后需要进行调整的四种情况 (1) 单向右旋平衡处理LL 当在左子树上插入左结点,使平衡因子由1增至2时 (2) 单向左旋平衡处理RR 当在右子树上插入右结点,使平衡因子由-1增至-2时 (3) 双向旋转(先左后右)平衡处理LR 当在左子树上插入右结点,使平衡因子由1增至2时 (4) 双向旋转(先右后左)平衡处理RL 当在右子树上插入左结点,使平衡因子由-1增至-2时 二叉排序树转成平衡树示例设关键字序列为(13,24,37,90,53) 例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6 例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6 失衡二叉排序树平衡化过程特性 h-1 -2 A 1 B -1 B 0 C CL AL h-2 h-1 RL 1 C h-1 CR 0 A AL BR CL CR BR 1、 树的高度不会增加；h＋1 2、 保持了二叉排序树的基本性质。 3、 使二叉排序查找性能趋近二分查找。 在平衡树上进行查找的过程和二叉排序树相同，因此在查找过程中和给定值进行比较的关键码个数不超过树的深度。为了确定含有n个关键码的平衡树的最大深度，先分析深度为h的平衡树所具有的最少结点数。 平衡二叉树查找性能分析 (查找＋插入＋平衡化） 斐波那契序列?： F0＝0，F1＝1，Fi＝Fi-1+ Fi-2 F0＝0，F1＝1，F2＝1, F3=2, F4=3, F5=5, F6=8, F7=13, F8＝21 假设以Nh表示深度为h的平衡树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。这个关系和斐波那契序列极为相似。利用归纳法容易证明：当h≥0.? 因此，在平衡二叉树上进行查找的时间复杂度为O(log2n)。 问：深度为6的平衡树最少具有多少结点？ 20 平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。 平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。 在插入新结点时，当确定了新结点应插入的位置后，需向上寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。 平衡二叉排序树编程实现注意事项 B-树的形态和本质 三 B－、B+树 1 11 35 1 1 18 1 27 1 99 64 53 3 47 78 43 2 1 39 F F F F F F F F F F F F 本质：多路查找树，查找过程类似于二叉排序树 非终端结点中包含下列信息数据（n，A0，K1， A1，K2，A2，…， Kn，An） B-树的定义或曰性质 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树： 1、 树中每个结点至多有m棵子树； 2、 若根结点不是叶子结点，则至少有两棵子树； 3、 除根之外的所有非终端结点至少有?m/2?棵子树； 4、 所有的非终端结点中包含下列信息数据（n，A0，K1， A1，K2，A2，…， Kn，An），其中Ki为关键字，关键字个数n 必须满足 ?m/2? －1=n=m-1。 5 、所有的叶子结点都出现在同一层次上，并且不带信息。 例：一棵四阶的B-树。 1 11 35 1 1 1