数据结构-第八章解析.ppt

平衡二叉树的插入 平衡二叉树插入结点的算法思想如下： （1）按二叉排序树的性质插入结点。 （2）如果插入结点之后出现不平衡的结点，则继续步骤（3）；否则插入完成。 （3）找到失去平衡的最小子树。 （4）判断平衡旋转的类型作相应平衡化处理。 在此算法中，有以下三个关键问题： 其一、如何发现插入后出现不平衡的结点呢？ 其二、如何确定失去平衡的最小子树呢？ 其三、又如何判断平衡旋转的类型呢？ 由平衡二叉树的定义可知，在插入之后如果树上出现平衡因子绝对值大于1的结点，则说明二叉排序树已不平衡。这时失去平衡的最小子树的根结点必为离插入结点最近，而且插入之前平衡因子绝对值为1的结点。 要解决上述三个问题可以如下处理： （1）在查找结点x的插入位置的过程中，记下从根结点到插入位置的路径上离插入位置最近的且平衡因子绝对值为1的结点，并令指针a指向该结点；如果此路径上不存在平衡因子绝对值为1的结点，则指针a指向根结点。 （2）对于从a结点到x结点的路径上的每一个结点（不包括结点x），根据结点中关键字和x的大小比较修改结点的平衡因子。如果结点关键字大于x，则结点平衡因子减1；否则结点平衡因子加1。 （3）如果结点a的平衡因子绝对值为2，则表示二叉排序树失去平衡，再根据结点a及其左右孩子的平衡因子值来确定平衡旋转的类型。 从空树开始，不断地用上述算法插入结点就可建立平衡二叉树。例如，输入关键字序列为{11、39、23、68、85、8、3、46、27、50}，右图给出了从空树开始按此顺序插入结点并进行调整的过程。 平衡二叉树的删除 在平衡二叉树上进行删除操作时，同样也需要考虑平衡化旋转问题。删除算法的思想如下： （1）如果被删结点x有左、右孩子，首先查找x在中序次序下的直接前驱y(同样也可以找直接后继)，再把结点y的内容传送给结点x，再删除结点y（结点y最多有一个孩子）。 （2）对于删除最多有一个孩子的结点x，可以简单地把x的双亲结点中原来指向x的指针改指到x的孩子结点。如果结点x没有孩子，则其双亲结点的相应指针置为空。 （3）对于从结点x的双亲到根结点的路径上的每一个结点P，当布尔变量shorter的值为true时，根据以下三种不同的情况继续步骤，直到布尔变量shorter的值为false时，整个删除算法结束。 （4）情况一，当结点p的平衡因子为0，如果它的左子树或右子树被缩短（shorter的值为true），则它的平衡因子改为1或-1，由于此时以结点p为根的子树高度没有缩短，所以置shorter的值为false。 （5）情况二，结点p的平衡因子不为0，且其较高的子树被缩短，则P的平衡因子改为0。由于此时以结点p为根的子树高度被缩短，所以shorter的值仍为true。 （6）情况三，结点p的平衡因子不为0，且较矮的子树又被缩短，则在结点p发生不平衡。此时，将进行平衡化旋转来恢复平衡。令结点P的较高子树的根结点为q，则根据结点p和q的平衡因子值，有如下三种平衡化操作。 1）如果q的平衡因子为0，则只要执行一个单旋转就可恢复结点p的平衡，由于旋转后被处理子树的高度没有缩短，所以置shorter的值为false。 2）如果q的平衡因子与p的平衡因子相同，则只要执行一个单旋转就可恢复结点p的平衡。由于此时被处理子树的高度被缩短，所以shorter的值仍为true。最后，结点p和q的平衡因子均改为0。 3）如果p与q的平衡因子的符号相反，则需要执行一个双旋转来恢复平衡，先围绕q转、再围绕p转。由于此时被处理子树的高度被缩短，所以shorter的值仍为true，新的根结点的平衡因子置为0，其它结点的平衡因子作相应处理。 平衡二叉树中删除结点后平衡旋转的示例 B—树 二叉排序树比较适合于在内存中组织较小的索引。对于存放在外存中的较大的文件系统，用二叉排序树来组织索引就不太合适了。若以结点作为内外存交换的单位，则在查找过程中需对外存进行log2n次访问，显然很费时。因此在文件检索系统中大量使用的是用B—树或B+树做文件索引。 动态的m路查找树 一棵m路查找树，它或者是一棵空树，或者是满足如下性质的树： （1）根结点最多有m棵子树，并具有如下的结构：（n、p0、k1、p1、k2、p2、…、kn、pn）其中，Pi是指向子树的指针，Ki是数据元素的关键字；1≤i≤n＜m。 （2）Ki＜Ki+1，1≤i＜n。 （3）在Pi所指的子树中所有的数据元素的关键字都小于K i+1，且大于K i，0in。 （4）在Pn所指的子树中所有数据元素的关键字都大于kn，而子树P0中的所有数据元素的关键字都小于K1。 （5）Pi所指的子树也是m路查找树，0≤i≤n。 下图是一棵3路查找树，它有9个数据元素。 对于