其余同B-树的查找类似B＋树的插入B.PPT

第九章 查找 else { //左右子树均不空 q = p; s = p－lchild; while (s－rchild) { //转左然后向右到尽头 q = s; s = s－rchild; } p－data = s－data; //s指向被删除结点的前驱 if (q != p) q－rchild = s－lchild; //重接*q的右子树 else q－lchild = s－lchild; //重接*q的左子树 delete s; } // else return TRUE; } // Delete 显然，P(0)=0, P(1)=1。 ⑤二叉排序树的查找分析 假设在含有n(n≥1)个关键字的序列中，i个关键字小于第一个关键字，n－i－1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为： （9－2） 其中，P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)＋1为查找 左子树中每个关键字时所用比较次数的平均值，P(n－i－1)＋1为查找右子 树中每个关键字时所用比较次数的平均值。 又，假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，……，或第n个的概率相同，则可对（9－2）式从i等于0至n－1取平均值： 容易看出上式括弧中的第一项和第二项对称。又，i＝0时iP(i)=0，则上式 可改写为： n≥2 （9－3） 由式（9－3）可推得： 由此可得 即 又 （9－4） 由递推公式（9－4）和初始条件P(1)=1可推得： 则当n≥2时： （9－5） （2）平衡二叉树 ①定义 平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称 AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子 树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不 超过1。 平衡因子BF（Balance Factor）：二叉树上结点的左子树的深度减去它的右子树的深度的值。 由平衡二叉树的定义易知，平衡二叉树上所有结点的平衡因子只可能 是－1、0和1。 例如，图9.6(a)所示为两棵平衡二叉树，而图 9.6(b)为两棵不平衡二叉树，结点中的值为该结点 的平衡因子 ②图形表示 (a) 平衡二叉树 1 1 0 0 -1 1 -1 0 1 0 0 -1 0 -2 0 1 0 0 2 -1 0 0 1 0 (b) 不平衡二叉树 图9.6 平衡与不平衡二叉树及结点的平衡因子 typedef struct BSTNode { ElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild; //左、右孩子指针 } BSTNode, * BSTree; ③C语言描述 假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的 指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)， 则失去平衡后进行调整的规律可归纳为下列4种情况： ④平衡调整 1．单向右旋平衡处理： 由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增 至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操 作。如图9.6(a)所示。 2．单向左旋平衡处理： 由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由－1 变为－2，致使以*a为根的子树失去平衡，则需进行一次向左的顺逆针旋 转操作。如图9.6(c)所示。 3．双向旋转（先左后右）平衡处理： 由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增 至2，致使以*a为根的子树失去平衡,则需进行两次旋转（先左旋后右旋） 操作。如图9.6(b)所示。 4．双向旋转（先右后左）平衡处理： 由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由－1变 为－2，致使以*a为根的子树失去平衡,则需进行两次旋转（先右旋后左旋） 操作。如图9.6(d)所示。 (a) LL型 BL BR AR 插入结点 2 A 1 B 0 A 0 B LL AR h-1 h BL