《数据结构与算法分析 C语言描述(第2版)Larry Nyhoff AVL树》由会员分享，可在线阅读，更多相关《数据结构与算法分析 C语言描述(第2版)Larry Nyhoff AVL树(15页珍藏版)》请在人人文库网上搜索。
1、或者是一棵空树 或者左右子树均为AVL树，且左右子树的深度 之差的绝对值不超过1 若定义二叉树上结点的平衡因子BF(Balance Factor) 为该结点的左子树的深度减去右子树的深度，那么 在AVL树上所有结点平衡因子只可能为-1, 0, 1 只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。 对AVL树来说，它的深度和logN同数量级，因此 我们希望任何初始序列构成的二叉查找树都 是 AVL树。,AVL树(平衡的二叉查找树),1,1,1,-1,0,0,0,-1,1,2,0,0,1,平衡二叉树和不平衡二叉树示例,设最小不平衡子树的根为A，调整的规律可归纳 为下列四种。
2、： 1. RR型调整(单右旋)； 2. LL型调整(单左旋) ； 3. LR型调整(先左后右双旋)； 4. RL型调整(先右后左双旋)； 上面的几种情况在经过平衡旋转处理后，以*b 或*c为根的新子树为平衡二叉树，而且它的深度和 插入之前以*a为根的子树相同。 因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行旋转处理。,指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树。,27,10,51,18,41,25,0,0,1,1,-1,-2,最小 不平衡子树,插入结点,最小不平衡子树:,RR型调整操作示意图 (B)A()= ()B(A) 调整规则将A的左子女B提升为新。
3、二叉树的根；原来的根A连同其右子树向右下旋转成为B的右子树；B的原右子树作为A的左子树。 插入项位于最近的平衡因子为+2的祖先结点的左孩子的左子树时使用。,27,10,0,1,B,A,27,10,0,1,B,A,05,2,27,10,0,0,B,A,05,0,51,27,0,1,B,A,10,0,05,18,0,0,03,0,1,1,2,51,27,0,B,A,10,0,05,18,0,03,0,1,0,RR型调整操作示例,LL型调整操作示意图 ()A(B)= (A)B() 调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。。
4、 插入项位于最近的平衡因子为-2的祖先结点的右孩子孩子的右子树时使用。,27,51,0,-1,B,A,27,51,0,-1,B,A,73,-2,73,51,0,0,B,A,27,0,51,27,0,-1,B,A,10,0,73,41,0,99,73,0,B,A,51,0,27,41,0,10,0,0,-1,LL型调整操作示例,0,99,0,-1,-1,-2,LR型调整操作示意图 ()B(C)A()= (B)C(A) 调整规则设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树向左下旋转成为新根C的左子树，原C的左子树成为B的右子树；原根A连同其右子树向右下旋。
5、转成为新根C的右子树，原C的右子树成为A的左子树。 插入项位于最近的平衡因子为+2的祖先结点的左孩子的右子树时使用。,51,27,0,1,B,A,10,0,05,18,0,0,C,51,27,0,C,A,18,0,10,16,0,05,0,0,-1,B,LR型调整操作示例,51,27,-1,B,A,10,0,05,18,0,1,C,16,0,-2,RL型调整操作示意图 ()A(C)B()= (A)C(B) 调整规则：设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树向右下旋转成为新根C的右子树，C的原右子树成为B的左子树；原来的根A连同其左子树向左下旋转。
6、成为新根C的左子树，原来C的左子树成为A的右子树。 插入项位于最近的平衡因子为-2的祖先结点的右孩子的左子树时使用。,51,27,0,-1,B,A,10,0,73,41,0,73,51,0,C,A,41,0,B,27,30,0,10,0,0,-1,RL型调整操作示例,0,0,0,-1,C,51,27,0,-1,B,A,10,0,73,41,1,0,30,0,0,1,-2,C,性能分析 含有n个结点的AVL树的高度是h= O(log2n)。插入结点的时间耗费最大为树的深度O(log2n)。 算法在查找插入结点的同时也找到最小不平衡子树。最小不平衡子树中平衡因子的最大调整时间为最小不平衡子树的深度。四种子树调整时间耗费为常数O( 1 )，因此 整个算法的时间复杂度为 O(log2n)。 关联容器通常采用AVL树作为存储结构。,练习,给出依次插入结点1、2、3、4、5、6、7、16、15后得到的AVL树。,二叉树上机,实现算法接受包含后缀表达式的字符串,并建立表达式树 tnode *buildExpTree(const string (将子树根的地址推到栈中，该栈的元素是tnode*类型) 使用displayTree()显示树 使用inorderOutput()遍历树，输出中缀表达式。
