第9章 查找表2.pptVIP

第九章 第2讲 二叉排序树举例 3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 二叉排序树的生成(插入结点) 二叉排序树的生成(连续进行插入操作) 例如:对{45,24,53,45,12,24,90} 关键字序列的二叉排序树生成过程如下: 二叉排序树结点的删除(保持二叉排序树的特性及次序) 设被删除的结点为*p,其父结点为*f,并不失一般性假设*p为*f的左孩子,则 (1)若*p为叶结点,即PL和PR均为空.直接删除不会影响树结构; (2)若*p只有PL或只有PR.只要令PL或PR直接成为其双亲结点*f的左孩子即可,这样也不会影响树结构; (3)若*p有PL也有PR.为保持中序遍历二叉树的序列不变,可以有两种处理方法:其一是令PL为*f的左子树,PR为*s的右子树(*s为中序遍历PL的最后一个结点);其二是令*p的直接前驱(或直接后继)*s替代*p,然后删除直接前驱(或直接后继)*s.若*s有左孩子则左孩子取代*s的位置.这样虽然影响了树结构,但不会影响中序遍历二叉树时的结点次序. 在二叉排序树中删除结点*p 二叉排序树的查找分析 n个结点的二叉排序树的平均查找长度和树的形态有关{45,24,53,12,37,93} 最坏情况是二叉排序树蜕变单支树:{12,24,37,45, 53,93} 二叉排序树举例(题目) 已知如下所示长度为12的表 (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度ASL; (2)若对表中元素先进行排序构成有序表,求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度; 二叉排序树举例(解答1) (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) 二叉排序树举例(解答2) (Apr,Aug,Dec,Fab,Jan,July,June,Mar,May,Nov,Oct,Sep) 二、 平衡二叉树(AVL) 什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树 左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF(Balance Factor)是左子树的深度减去右子树的深度,它只可能是 -1, 0, 1 平衡二叉树(也称AVL树)的深度为O(logn)(其中n为结点个数) 它的平均查找长度也是O(logn) 平衡二叉树及平衡因子举例 不平衡二叉树及平衡因子举例 二叉排序树转成平衡树示例设关键字序列为(13,24,37,90,53) 二叉排序树转成平衡树失去平衡后进行调整的四种情况 (1)单向右旋平衡处理 当在左子树上插入左结点,使平衡因子由1增至2时 (2)单向左旋平衡处理(上例从图(d)到图(e)) 当在右子树上插入右结点,使平衡因子由-1增至-2时 (3)双向旋转(先左后右)平衡处理 当在左子树上插入右结点,使平衡因子由1增至2时 (4)双向旋转(先右后左)平衡处理 当在右子树上插入左结点,使平衡因子由-1增至-2时 (例如上例从图(f)右旋到图(g)再左旋到图(h)) B-树构成 一 棵m阶的B-树，或为空树，或为满足下列特性的m叉树： 1、树中每个结点至多有m棵子树； 2、若根结点不是叶子结点，则至少有2棵子树； 3、除根之外的所有非终端结点至少有m/2棵子树； 4、所有非终端结点中包含下列信息数据（n,A0,K1,K2,……Kn,An） 5、所有叶子结点都出现在同一层次上，并且不带信息（实际上这些结点不存在，指向的指针为空）。 平衡树的特性 树中所有叶子结点均不带信息，且在树中的同一层次上； 根结点或为叶子结点，或至少含有两棵子树； 其余所有非叶结点均至少含有?m/2?棵子树，至多含有 m 棵子树； typedef struct BTNode { int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; // 关键字（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量 } BTNode, *BTree; // B树结点和B树的类型 B-树结构的C语言描述如下: