第7章查找概要.ppt

int Search_Bin ( SSTable ST , KeyType key) { low = 1; high = ST.length; while ( low = high ) { mid = ( low + high ) / 2 ; if ( key == ST.R[mid].key ) return mid; else if ( key ST.R[mid].key ) high=mid-1; else low = mid + 1 ; } return 0; } * {10， 18， 3， 8， 12， 2， 7} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 二叉排序树的操作－生成 * 不同插入次序的序列生成不同形态的二叉排序树 40 24 55 12 37 12 24 37 40 55 40，24，12，37，55 12，24，37，40，55 二叉排序树的操作－生成 * 二叉排序树的操作－删除 将因删除结点而断开的二叉链表重新链接起来 防止重新链接后树的高度增加 * * 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。 被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。 * 第i层结点需比较i次。在等概率的前提下，上述两图的平均查找长度为： 40 24 55 12 37 12 24 37 40 55 查找的性能分析 * 平均查找长度和二叉树的形态有关，即， 最好：log2n（形态匀称，与二分查找的判定树相似） 最坏: （n+1)/2（单支树） 查找的性能分析 40 24 55 12 37 12 24 37 40 55 * 问题：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值≤ 1 平衡二叉树 平衡因子:该结点左子树与右子树的高度差 * 任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树； 对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。 * (a) 平衡树 (b) 不平衡树 练习：判断下列二叉树是否AVL树？ 0 0 0 1 1 -1 -1 2 0 0 0 1 -1 * 如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。 LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转 保证二叉排序树的次序不变 * 若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。 (以B为旋转轴） A B C A B C 若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。 (以B为旋转轴） 2）RR平衡旋转： A B C A B C 1）LL平衡旋转： * 若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。 (以插入的结点C为旋转轴） 4）RL平衡旋转： A B C A B C A B C 若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。 (以插入的