第11章 有哪些信誉好的足球投注网站树(一).ppt

删除p * 判断平衡性 * 上一级仍然不平衡 * 最终结果 * AVL删除小结 不平衡共分三种情况 一次旋转即停止 一次旋转不平衡 两次旋转不平衡 关键是考察不平衡节点的另一棵子树！ * 一次旋转即停止 * 一次旋转不平衡 * 两次旋转不平衡 * 练习 在如图AVL树中依次删除22,3,10,9，画出每步处理后树的形态 * 17 13 22 9 16 27 15 20 12 3 10 18 * AVL树的高度（续） |Fh|+1=|Fh-1|+1+|Fh-2|+1：菲波那契数列！ h≈1.44log2|Fh|=l.44log2n=O(logn) * 关于AVL树的一组值 高度为h的AVL树最少有几个节点？ * h 1 2 3 4 5 6 7 …… MinNum 1 1+1 1+2+1 2+4+1 4+7+1 7+12+1 12+20+1 …… 1 2 4 7 12 20 33 …… AVL树的描述 与BSTree类相似，增加平衡因子域bf 左子树的高度-右子树的高度 * 请写出下述各节点的平衡因子 * AVL有哪些信誉好的足球投注网站 与一般的二叉有哪些信誉好的足球投注网站树一致 从根节点开始将key与节点值比较 如果key小于节点值，进入左子树； 如果key大于节点值，进入右子树； 直到找到或子树为空停止。 * AVL插入 首先利用二叉有哪些信誉好的足球投注网站树的插入算法 可能出现不平衡的情况?调整结构 插入32后的调整 * 插入导致的不平衡树的特性 不平衡树中的平衡因子的值限于-2，-1，0，1和2 平衡因子值为2的节点，在插入前其平衡因子为1类似的，平衡因子值为-2的，插入前为-1 * 插入导致的不平衡树的特性 只有从根到新插入节点路径上的节点，其平衡因子才会在插入操作后发生改变 假设A是离新插入节点最近的，平衡因子为-2或2的祖先节点，则在插入前，从A到新插入节点的路径上，所有节点的平衡因子都是0 * 寻找“A”－寻找“X” 插入操作前，bf(A)必然为1或-1 X——这样的节点中的“最后”一个 32插入右图，X——40 * 寻找“A” －寻找“X” 22、28、50插入左图，X——25 10、14、16、19插入左图，X——不存在 X不存在——bf值全为0，插入不会导致不平衡 * X未变为A——插入后平衡 X的后代节点bf值全为0?插入后子树高度必然发生改变?X的bf值必然发生改变，变化为±1 * X未变为A——插入后平衡 ?仍旧平衡的唯一可能——插入后bf(X)=0 ?插入前后以X为根的子树的高度未改变 ?新元素必然插入原来较矮的那棵子树 * X变为A?找到了A bf值由-1变为-2（或1变为2） ?新节点插入了较高的那棵子树 L型不平衡：左子树较高，新节点插入左子树 LL：新节点插入左子树的左子树 LR：插入左子树的右子树 R型不平衡：RL、RR * LL型不平衡及其调整方法 旋转后保持有哪些信誉好的足球投注网站树特性 BLBBRAAR 单旋转：RR——对称的 * 单旋转例 * LR型不平衡及其调整方法 b=0（CL高度h，CR高度h）?bf(B)=bf(A)=0b=1（CL高度h，CR高度h-1）?bf(B)=0, bf(A)=-1b=-1（CL高度h-1，CR高度h）?bf(B)=1, bf(A)=0 RL——对称 * 双旋转例 * 双旋转例 * AVL树插入算法 从根节点开始有哪些信誉好的足球投注网站，确定插入位置 同时寻找最后的平衡因子为-1或1的节点，记为A 若找到相同关键字的元素，插入失败 若没有这样的节点A——插入后平衡 从根节点重新遍历一次，修改平衡因子，然后终止 * AVL树插入算法 若bf(A)=1且新节点插入A的右子树，或bf(A)=-1且新节点插入A的左子树?A 的新平衡因子是0 修改从A 到新节点路径中节点的平衡因子，然后终止 不平衡情况 确定不平衡类型，并执行相应的旋转 在从新子树根节点至新插入节点路径中，根据旋转需要修改相应的平衡因子 * AVL插入小结 不平衡共分四种情况 LL与RR对称：一次旋转 LR与RL对称：两次旋转 关键是找到距离插入点最近的不平衡节点！ * 一次旋转示例（RR） * 两次旋转示例（RL） * 小练习 请将元素52插入到如下AVL树中，生成新的AVL树 * 45 12 53 100 50 练习 设有一个关键字序列{55,31,11,37,46,73,63,2,7} 从空树开始构造平衡二叉树，画出每加入一个新节点时二叉树的形态。若发生不平衡，指明需做的旋转类型及旋转结果 计算最终平衡二叉树在等概率下的查找成功平均查找长度和查找不成功平均查找长度 * AVL删除 首先执行二叉有哪些信誉好的足球投注网站树的删除，如不平衡则调整 从删除节点的父节点开始到根节点，对路径上的每个节点q，根据新的平衡因子，判断子树高度变化，调整方法，以及是否继续调整过程