资源描述：
《数据结构（牛小飞）平衡二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、平衡二叉树平衡二叉树的定义平衡二叉树的构造平衡二叉树的查找性能分析小结和作业课堂练习程序讲解P120,4.21AVL(Adelson-Velskii和Landis)树是带有平衡条件的二叉查找树。平衡二叉树的定义一棵AVL(Adelson-Velskii和Landis)树是其每个节点的左子树和右子树的高（深）度最多差1的二叉查找树，即空树的高度定义为-1。hL-hR<=1节点的平衡因子：该节点的左子树的深度减去它的右子树的深度平衡二叉树所有节点的平衡因子只可能为：-1，0，1。平衡二叉树的定义54821非平衡二叉树平衡因子>10122
2、054820011平衡因子<=1平衡二叉树平衡二叉树的定义52814377281435非平衡二叉树平衡二叉树平衡二叉树的定义单旋转举例造成不平衡的原因双旋转平衡二叉树的构造当向一个AVL树中插入一个新节点是，有可能破坏AVL树的特性。平衡二叉树的构造如果发生这种情况，就需在插入完成之前恢复平衡的性质。我们称恢复调整的过程为旋转(rotation)52814376将会破坏关键字为8的节点处的平衡。将6插入到AVL树中即关键字为8的节点必须重新平衡。我们把必须重新平衡的节点叫做α。由于任意节点最多有两个孩子，因此出现高度不平衡就需要α点
3、的两棵子树的高度差2。平衡二叉树的构造造成α不平衡的原因有下面几种情况：1.对α的左孩子的左子树进行一次插入。2.对α的左孩子的右子树进行一次插入。3.对α的右孩子的左子树进行一次插入。4.对α的右孩子的右子树进行一次插入。LL型LR型RL型RR型ABCX2LLABCX2LRABCX-2RRABCX-2RL平衡二叉树的构造一、插入发生在“外边”的情况，即LL型和RR型平衡方案：单旋转(singlerotation)平衡二叉树的构造-平衡方案二、插入发生在“内部”的情况，即LR型和RL型平衡方案：双旋转(doublerotation)
4、ABBLBRARABBLARh-1h-1h-1h-1平衡二叉查找树插入x后不再平衡ABBLBRARhh-1X平衡二叉树的构造-单旋转一、单旋转-LL型12抓住节点B往上拽使之成为根节点，自然，A成为了B的右孩子，BL,AR的性质不变，BR成为了A的左孩子。ABBLBRARhh-1XBABRBLhXARh-1一、单旋转-LL型的调整过程AL平衡二叉树的构造-单旋转右旋转-1AALh-1BRABBLh-1AALh-1-2BRABBLhX一、单旋转-RR型插入x后不再平衡平衡二叉查找树平衡二叉树的构造-单旋转AALh-1-2BRABBLh
5、XALh-10BBLABRhX一、单旋转-RR型的调整过程抓住节点B往上拽使之成为根节点，自然，A成为了B的左孩子，BR,AL的性质不变，BL成为了A的右孩子。AL平衡二叉树的构造-单旋转左旋转从空AVL树开始依次插入关键字3,2,1,4,5,6,7321插入223插入1324LL型，右旋转31插入4231插入554231RR型，左旋转24153单旋转举例24153插入6241536RR型，左旋转465213从空AVL树开始依次插入关键字3,2,1,4,5,6,7单旋转举例465213插入77465213RR型，左旋转7564213
6、从空AVL树开始依次插入关键字3,2,1,4,5,6,7单旋转举例h-1BCRABBLARh-1CCLX2平衡二叉树的构造-双旋转一、双旋转-LR型1h-2CRABBLARh-1CCL插入x后不再平衡平衡二叉查找树先在A的左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转CRBLAARh-1CBh-1CLX2h-1CRABBLARh-1CCL2X平衡二叉树的构造-双旋转一、双旋转-LR型的调整过程CRAARh-1Ch-1BBLCLX2ACh-1BBLCLX0CRARh-1平衡二叉树的构造-双旋转一、双旋转-LR型的调整过程先在A的
7、左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转-1AALh-1BRABCLCRCh-2Xh-1-2平衡二叉树的构造-双旋转一、双旋转-RL型插入x后不再平衡平衡二叉查找树ALh-1BRABCLCRCAALh-1BRABCLCRCXh-1-2ALh-1ABBRCCLCRXh-1-2平衡二叉树的构造-双旋转先在A的右儿子和孙子之间右旋转，再在A和它的新儿子之间左旋转一、双旋转-RL型的调整过程AALh-1BRABCLCRCXh-1-2ALh-1CLCABRBCRXh-10平衡二叉树的构造-双旋转先在A的右儿子和孙子之间右旋转，再在
8、A和它的新儿子之间左旋转一、双旋转-RL型的调整过程例如:依次插入关键字5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转平衡二叉树的构造—举例42658942689向左旋转一次继续插入关键字95平衡二叉
