数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

或者是一棵空树或者左右子树均为AVL树，且左右子树的深度之差的绝对值不超过1若定义二叉树上结点的平衡因子BF(BalanceFactor)为该结点的左子树的深度减去右子树的深度，那么在AVL树上所有结点平衡因子只可能为-1,0,1只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。对AVL树来说，它的深度和logN同数量级，因此我们希望任何初始序列构成的二叉查找树都是AVL树。AVL树(平衡的二叉查找树）111-1000-112001平衡二叉树和不平衡二叉树示例设最小不平衡子树的根为A，调整的规律可归纳为下列四种：1.RR型调整（单右旋）；2.LL型调整（单左旋）；3.LR型调整（先左后右双旋）；4.RL型调整（先右后左双旋）；上面的几种情况在经过平衡旋转处理后，以*b或*c为根的新子树为平衡二叉树，而且它的深度和插入之前以*a为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行旋转处理。指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树。2710511841250011-1-2最小不平衡子树插入结点最小不平衡子树:AABBBAγhγhh+1αhαhβhαhβhβγh102100RR型调整操作示意图(αBβ)A(γ)=(α)B(βAγ)调整规则∶将A的左子女B提升为新二叉树的根；原来的根A连同其右子树γ向右下旋转成为B的右子树；B的原右子树β作为A的左子树。插入项位于最近的平衡因子为+2的祖先结点的左孩子的左子树时使用。271001BA271001BA052271000BA050512701BA10005180003011251270BA1000518003010RR型调整操作示例AABBBAαhαhh+1γhβhγhβhγhαβh-1000-2-1LL型调整操作示意图(α)A(βBγ)=(αAβ)B(γ)调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。插入项位于最近的平衡因子为-2的祖先结点的右孩子孩子的右子树时使用。27510-1BA27510-1BA73-2735100BA27051270-1BA1007341099730BA510274101000-1LL型调整操作示例0990-1-1-2AACBBBAδhδhCChαhαhαβhγh-1δhh-1βγh-1hβγh-1120-10-1001LR型调整操作示意图((α)B(βCγ))A(δ)=(αBβ)C(γAδ)调整规则∶设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树α向左下旋转成为新根C的左子树，原C的左子树β成为B的右子树；原根A连同其右子树δ向右下旋转成为新根C的右子树，原C的右子树γ成为A的左子树。插入项位于最近的平衡因子为+2的祖先结点的左孩子的右子树时使用。512701BA100051800C51270CA180101600500-1BLR型调整操作示例5127-1BA100051801C160-2AACBBABhαhαδCCδhδhhαβhγh-1δhh-1βγh-1hβγh-10-100-101-201RL型调整操作示意图(α)A((βCγ)B(δ))=(αAβ)C(γBδ)调整规则：设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树δ向右下旋转成为新根C的右子树，C的原右子树γ成为B的左子树；原来的根A连同其左子树α向左下旋转成为新根C的左子树，原来C的左子树β成为A的右子树。插入项位于最近的平衡因子为-2的祖先结点的右孩子的左子树时使用。51270-1BA1007341073510CA410B273001000-1RL型调整操作示例000-1C51270-1BA10073411030001-2C性能分析含有n个结点的AVL树的高度是h=O(log2n)。插入结点的时间耗费最大为树的深度O(log2n)。算法在查找插入结点的同时也找到最小不平衡子树。最小不平衡子树中平衡因子的最大调整时间为最小不平衡子树的深度。四种子树调整时间耗费为常数O(1)，因此整个算法的时间复杂度为O(log2n)。关联容器通常采用AVL树作为存储结构。练习给出依次插入结点1、2、3、4、5、6、7、16、15后得到的AVL树。二叉树上机实现算法接受包含后缀表达式的字符串,并建立表达式树tnodechar*buildExpTree(conststring&pexp);(将子树根的地址推到栈中，该栈的元素是tnodechar*类型)使用displayTree()显示树使用inorderOutput()遍历树，输出中缀表达式