数据结构复习15201210数据结构考研复习2201210章节幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 　　　　if (q != p ) q-rchild = s-lchild; 　　　 else q-lchild = s-lchild; 　 // 重接 *q 的左子树　　　 delete s; 　　 }// else } // DeleteNode 6 二叉排序树 （4）查找性能分析 从二叉排序树的查找过程可见，二叉排序树的查找性能取决于它的深度。 然而由于二叉排序树是在查找过程中逐个插入构成，因此它的深度取决于关键字先后插入的次序。 6 二叉排序树 　　 例如，含关键字1,2,3,4,5的二叉排序树，其深度可能为3或4或5，若按1,2,3,4,5的次序得到的二叉排序树的深度为5，若按3,1,2,4,5的次序得到的二叉排序树的深度则为3。 6 二叉排序树 2 1 3 4 5 ASL =（1+2+3+4+5）/ 5 = 3 3 5 4 1 2 ASL =（1+2+3+2+3）/ 5 = 2.2 6 二叉排序树 ?二叉排序树查找的平均性能 平均查找长度的含义即为进行一次查找所需进行 “比较”的平均次数，则 P(n) 表示在含有 n 个结点的二叉排序树上进行一次查找操作时关键字和给定值进行比较的平均次数。 在随机的情况下，二叉排序树的查找性能是和 log n 等数量级的。 6 二叉排序树  假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度： 6 二叉排序树  在等概率查找的情况下 6 二叉排序树 □ 平衡二叉排序树 当生成二叉排序树的关键字序列非随机时，所生成的二叉排序树有可能偏向于单支，从而使其查找性能接近于顺序表。在这种情况下，需要在生成二叉排序树的过程中进行“平衡化”处理，使得在任何时刻二叉排序树的形态都是“平衡”的。 7 平衡二叉树 ?平衡因子 平衡因子定义为平衡二叉树中左子树的深度减去右子树的深度。 ?平衡二叉树的概念 称二叉排序树为“平衡”指的是，它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉排序树，且左右子树深度之差的绝对值不大于1。 7 平衡二叉树 ?平衡二叉排序树的构造 每当插入一个结点时,首先检查是否因插入而破坏了树的平衡性, 如果是因插入结点而破坏了树的平衡性, 则找出其中最小不平衡子树, 在保持排序树特性的前提下, 调整最小不平衡子树中各结点之间的连接关系, 以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。 7 平衡二叉树 ?最小不平衡子树 所谓最小不平衡子树是指: 以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。可归纳为下列四种情况: ① LL型 ② RR型 ③ LR型 ④ RL型  　 7 平衡二叉树 ① LL型 调整前 A-bf=2；B-bf=1； B=A-lchild； 调整后 A-lchild=B-rchild； B-rchild=A； A-bf=0；B-bf=0； 7 平衡二叉树 ② RR型 调整前 A-bf=-2；B-bf=-1； B=A-rchild； 调整后 A-rchild=B-lchild； B-lchild=A； A-bf=0；B-bf=0； 7 平衡二叉树 ?调整根结点B的指针 调整后二叉树的根结点B应接回原A处。令A原来的父指针为FA，如果FA非空，则用B代替A做FA的左孩