Chapter11-2-AVL树及其应用.ppt

Chapter11 有哪些信誉好的足球投注网站树 中国地质大学信息工程学院 内容提要 11.1 二叉有哪些信誉好的足球投注网站树 11.2 AVL树 11.3 红黑树 11.4 B-树 11.5 应用 1、为什么引入“平衡二叉树” 2、平衡二叉树的定义 平衡树（Balanced Tree）：高度为O(logn)的树。 平衡二叉树（Balanced Binary Tree）：由阿德尔森一维尔斯和兰迪斯（Adelson-Velskii and Landis）于1962年首先提出的，所以又称为AVL树。 平衡二叉树的定义 空二叉树是AVL树； 如果T是一棵非空的二叉有哪些信誉好的足球投注网站树，TL和TR分别是其左子树和右子树，那么当T满足以下条件时，T是一棵AVL树： 1）TL和TR 是AVL树； 2）|hL-hR|≤1，hL和hR分别是左子树和右子树的高度 AVL树必须具备的特征 n个元素的AVL树的高度是O(logn)； 一棵n元素的AVL有哪些信誉好的足球投注网站树能在O(高度)=O(logn) 的时间内完成有哪些信誉好的足球投注网站； 将一个新元素插入到一棵n元素的AVL有哪些信誉好的足球投注网站树中，可得到一棵n+1元素的AVL树，这种插入过程可以在O(logn)时间内完成； 从一棵n元素的AVL有哪些信誉好的足球投注网站树中删除一个元素，可得到一棵n-1元素的AVL树，这种删除过程可以在O(logn)时间内完成。 3、AVL树的高度 假设Nh是一棵高度为h的AVL树中最小的节点数 可以看到Nh的定义与斐波那契数列的定义非常相似 4、AVL树的平衡因子 为每个节点增加一个平衡因子bf。节点x 的平衡因子bf (x)定义为：bf (x)= hL-hR 。 即：x的左子树的高度-x 的右子树的高度。 从AVL树的定义可以知道，平衡因子的可能取值为-1、0、1。 5、AVL树的有哪些信誉好的足球投注网站 如果一棵AVL树有n个节点，其高度可以保持在O(logn)，因此平均有哪些信誉好的足球投注网站长度也可以保持在O(logn)。 二叉有哪些信誉好的足球投注网站树的算法完全适用于AVL树。 6、AVL树的插入 若一棵二叉有哪些信誉好的足球投注网站树是平衡二叉树，插入某个节点后，可能会变成非平衡二叉树； 【解决办法】对该二叉树进行平衡处理，使其变成一棵平衡二叉树。 非AVL树的平衡化处理 每插入一个新节点时，AVL树中相关节点的平衡状态会发生改变。 因此，在插入一个新节点后，需要从插入位置沿通向根的路径回溯，检查各节点的平衡因子（左、右子树的高度差）； 如果在某一节点发现高度不平衡，停止回溯； 从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点，做平衡化旋转。 平衡化旋转 平衡化旋转有两类： 单旋转（LL旋转和LR旋转） 双旋转（LR旋转和RL旋转） 如果这三个节点处于一条直线上，则采用单旋转进行平衡化。 如果这三个节点处于一条折线上，则采用双旋转进行平衡化。 平衡化旋转（续） 平衡化旋转（续） 平衡化旋转（续） （1）LL旋转：顺时针 LL旋转的算法 （2）RR旋转：逆时针 左单旋转的算法 （3）LR旋转：先左后右双旋转 LR旋转演示 （4）RL旋转：先右后左双旋转 建立一棵AVL树 从一棵空树开始，通过输入一系列对象的关键值，逐步建立AVL树，在插入新节点时使用前面所给的算法进行平衡旋转。 例：输入关键值序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，构造一棵AVL树 课后练习1：画图 设有一个关键码的输入序列{ 55，31，11，37，46，73，63，02，07 }， 要求：从空树开始构造平衡二叉树，画出每加入一个新节点时二叉树的形态。若发生不平衡，指明需要做的平衡旋转类型及平衡旋转结果。 7、AVL树的删除 现象1 如果q新的平衡因子bf(q)=0，意味着删除前bf(q)=1或者bf(q)=-1，只有单子树 此时高度减1，需改变父节点和其他某些祖先节点的平衡因子 现象2 如果q新的平衡因子bf(q)=1或-1，意味着删除前bf(q)=0，左右子树高度一样 此时高度不变，需改变父节点和其他某些祖先节点的平衡因子 现象3 如果q新的平衡因子bf(q)=-2或2，意味着删除前bf(q)=-1或1，左右子树高度不同 此时树在q节点是不平衡的，需要平衡化处理 平衡因子为2或-2的两种情况 设A是第一个删除后bf(A)=2的节点，则删除前bf(A)=1，B为A的左子树的根节点； 根据节点B的平衡因子，bf(B)=0、1、-1； L型不平衡：删除发生在A的左子树，又可细分为L0、L1、L-1三种； R型不平衡：删除发生在A的右子树，又可细分为R0、R1、R-1三种； R0表示删除发生在A的右子树且bf(B)=0。 R1表示删除发生在A的右子树且bf(B)=1。 R-1表示删除发生在A的右子树且bf(B)=-1。 R0类型的平衡化处理 删除发生在A的右子树 且 bf(B) = 0 与LL型旋转类似，区别在于仅在于A和