数据结构(牛小飞)平衡二叉树.ppt

平衡二叉树,平衡二叉树的定义,平衡二叉树的构造,平衡二叉树的查找性能分析,小结和作业,课堂练习,程序讲解P120,4.21,AVL(Adelson-Velskii和Landis)树是带有平衡条件的二叉查找树。,平衡二叉树的定义,一棵AVL(Adelson-Velskii和Landis)树是其每个节点的左子树和右子树的高（深）度最多差1的二叉查找树，即,空树的高度定义为-1。,节点的平衡因子：该节点的左子树的深度减去它的右子树的深度,平衡二叉树所有节点的平衡因子只可能为：-1，0，1。,平衡二叉树的定义,非平衡二叉树,0,1,2,2,0,0,0,1,1,平衡二叉树,平衡二叉树的定义,非平衡二叉树,平衡二叉树,平衡二叉树的定义,单旋转,举例,造成不平衡的原因,双旋转,平衡二叉树的构造,当向一个AVL树中插入一个新节点是，有可能破坏AVL树的特性。,平衡二叉树的构造,如果发生这种情况，就需在插入完成之前恢复平衡的性质。我们称恢复调整的过程为旋转(rotation),将会破坏关键字为8的节点处的平衡。,将6插入到AVL树中,即关键字为8的节点必须重新平衡。,我们把必须重新平衡的节点叫做。由于任意节点最多有两个孩子，因此出现高度不平衡就需要点的两棵子树的高度差2。,平衡二叉树的构造,造成不平衡的原因有下面几种情况：,1.对的左孩子的左子树进行一次插入。,2.对的左孩子的右子树进行一次插入。,3.对的右孩子的左子树进行一次插入。,4.对的右孩子的右子树进行一次插入。,LL型,LR型,RL型,RR型,平衡二叉树的构造,一、插入发生在“外边”的情况，即LL型和RR型 平衡方案：单旋转(single rotation),平衡二叉树的构造-平衡方案,二、插入发生在“内部”的情况，即LR型和RL型 平衡方案：双旋转(double rotation),A,B,BL,BR,AR,A,B,BL,AR,平衡二叉查找树,插入x后不再平衡,A,B,BL,BR,AR,X,平衡二叉树的构造-单旋转,一、单旋转-LL型,1,2,抓住节点B往上拽使之成为根节点，自然，A成为了B的右孩子，BL,AR的性质不变，BR成为了A的左孩子。,A,B,BL,BR,AR,X,B,一、单旋转-LL型的调整过程,平衡二叉树的构造-单旋转,右旋转,-1,A,AL,h-1,BR,A,B,BL,A,AL,h-1,-2,BR,A,B,BL,X,一、单旋转-RR型,插入x后不再平衡,平衡二叉查找树,平衡二叉树的构造-单旋转,A,AL,h-1,-2,BR,A,B,BL,h,X,0,B,一、单旋转-RR型的调整过程,抓住节点B往上拽使之成为根节点，自然，A成为了B的左孩子，BR,AL的性质不变，BL成为了A的右孩子。,平衡二叉树的构造-单旋转,左旋转,从空AVL树开始依次插入关键字3,2,1,4,5,6,7,插入2,2,3,插入1,LL型，右旋转,插入4,2,插入5,2,RR型，左旋转,2,单旋转举例,插入6,RR型，左旋转,4,从空AVL树开始依次插入关键字3,2,1,4,5,6,7,单旋转举例,插入7,RR型，左旋转,从空AVL树开始依次插入关键字3,2,1,4,5,6,7,单旋转举例,B,CR,A,B,BL,AR,C,CL,X,2,平衡二叉树的构造-双旋转,一、双旋转-LR型,插入x后不再平衡,平衡二叉查找树,先在A的左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转,C,2,平衡二叉树的构造-双旋转,一、双旋转-LR型的调整过程,2,C,0,平衡二叉树的构造-双旋转,一、双旋转-LR型的调整过程,先在A的左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转,-1,A,AL,h-1,BR,A,B,CL,CR,C,h-2,X,-2,平衡二叉树的构造-双旋转,一、双旋转-RL型,插入x后不再平衡,平衡二叉查找树,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,-2,平衡二叉树的构造-双旋转,先在A的右儿子和孙子之间右旋转，再在A和它的新儿子之间左旋转,一、双旋转-RL型的调整过程,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,C,0,平衡二叉树的构造-双旋转,先在A的右儿子和孙子之间右旋转，再在A和它的新儿子之间左旋转,一、双旋转-RL型的调整过程,例如:依次插入关键字5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向左旋转,平衡二叉树的构造举例,9,向左旋转一次,继续插入关键字 9,5,平衡二叉树的构造举例,平衡二叉树的查找性能分析,在平衡树上进行查找的过程和二叉查找树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。,问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？,n=0,空树,最大深度为0,n=1,最大深度为1,n=2,最大深度为2,平衡二叉树的查找性能分析,n=3?,n=4,最大深度为3,n=7,最大深度为 4,平衡二叉树的查找性能分析,1.44log(n+2)-1.328,n=5,6?,反过来问，深度为h 的二叉平衡树中所含节点的最小值Nh是多少？,h=0,N0=0,h=1,h=2,h=3,N1=1,N2=2,N3=4,一般情况下，,Nh=Nh-1+Nh-2+1,利用归纳法可证得，,Nh=Fh+2-1,平衡二叉树的查找性能分析,3）因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和 log(n)相当。,1）由此推得，深度为 h 的二叉平衡树中所含节点的最小值 Nh=h+2/5-1,平衡二叉树的查找性能分析,课堂练习,2、按次序输入关键字：e,i,p,k,m,l,b，试画出AVL树的构造和调整过程。并求其在等概率的情况下查找成功的平均查找长度。,1、按次序输入关键字：1,2,3,4,5,6,7，试画出AVL树的构造和调整过程。,程序讲解-节点构造,privat static class AvlNode/二叉链表结构,AvlNode(AnyType theElement),element=theElement;left=right=null;,AnyType element;AvlNode left,right;int height;,AvlNode(AnyType theElement,AvlNode lt,AvlNode lr),element=theElement;left=lt;right=rt;height=0;,程序讲解-节点构造,privat static class AvlNode/二叉链表结构,private int height(AvlNode t),AnyType element;AvlNode left,right;int height;,return t=null?-1:t.height;,A,B,A,B,AR,AR,BR,BR,X,BL,程序讲解-单旋转,AvlNode B=A.left;,A.left=B.right;B.right=A;,LL型：围绕左孩子单旋转,A.height=Math.max(height(B.left),height(A.right)+1;,B.height=Math.max(height(B.left),A.height)+1;,2,1,0,0,private AvlNode rotateWithLeftChild(AvlNode A)/LL型，右旋转,AvlNode B=A.left;,A.height=Math.max(height(B.left),height(A.right)+1;,B.height=Math.max(height(B.left),A.height)+1;,A.left=B.right;B.right=A;,return B;,程序讲解-单旋转,A,B,A,B,X,AL,BL,BR,X,BR,BL,AL,AvlNode B=A.right;,A.right=B.left;B.left=A;,RR型：围绕右孩子单旋转,A.height=Math.max(height(A.left),height(B.left)+1;,B.height=Math.max(height(B.right),A.height)+1;,程序讲解-单旋转,-2,-1,0,0,private AvlNode rotateWithRightChild(AvlNode A)/RR型，左旋转,AvlNode B=A.right;,A.right=B.left;B.left=A;,return B;,程序讲解-单旋转,A.height=Math.max(height(A.left),height(B.left)+1;,B.height=Math.max(height(B.right),A.height)+1;,A,B,AR,h-1,CR,2,-1,C,BL,1,A,B,AR,CR,C,BL,CL,0,-1,0,CL,h-2,LR型：先以C为根左旋转，再以C为根右旋转,A,B,AR,CR,C,BL,CL,0,2,2,程序讲解-双旋转,rotateWithLeftChild(B),rotateWithRightChild(A),rotateWithLeftChild(A.left),(a),A,B,AR,h-1,2,-1,C,BL,-1,A,B,AR,CL,C,BL,CR,1,0,0,CR,CL,(b),A,B,AR,CL,C,BL,CR,1,2,1,程序讲解-双旋转,A,B,AR,h-1,CR,2,-1,C,BL,CL,0,A,B,AR,CR,C,BL,CL,0,0,0,(c),A,B,AR,CR,C,BL,CL,0,2,1,程序讲解-双旋转,private AvlNode doubleWithLeftChild(AvlNode A),A.left=rotateWithLeftChild(A.left);,程序讲解-双旋转,return rotateWithRightChild(A);,/LR型，先左旋转，后右旋转,对于RL型，同理可得到doubleWithRightChild()方法，详见课本100页，4-43,private AvlNode insert(AnyType x,AvlNode t),程序讲解-主程序,if(compareResult0)/插入到右子树else;/已存在项x，不进行任何处理,if(t=null)/空树,return new AvlNode(x,null,null);,int compareResult=compare(x,t.element);,return t;,程序讲解-主程序,/插入到t的左子树,t.left=insert(x,t.left);,if(height(t.left)-height(t.right)=2),if(compare(x,t.left.element)0),t=rotateWithLeftChild(t);,else,t=doubleWithLeftChild(t);,/需平衡的情况,/LL型,LR型,/原来左子树高，插入到左子树后更高，需要平衡/原来平衡，插入左子树后，则长高/原来左子树低，插入一个节点后左子树长高，则平衡,程序讲解-主程序,/插入到t的右子树,t.right=insert(x,t.right);,if(height(t.right)-height(t.left)=2),if(compare(x,t.right.element)0),t=rotateWithRightChild(t);,else,t=doubleWithRightChild(t);,/需平衡的情况,/RR型,RL型,/原来右子树高，插入到右子树后更高，需要平衡/原来平衡，插入右子树后，则长高/原来右子树低，插入一个节点后右子树长高，则平衡,小结和作业,平衡二叉树,1.平衡二叉树的定义,2.如何建立平衡二叉树,3.构造平衡二叉树的基本操作,4.平衡二叉树查找的性能分析,1.LL,2.LR,3.RR,4.RL,作业：P120,4.19,