1、平衡二叉树平衡二叉树平衡二叉树的定义平衡二叉树的构造平衡二叉树的查找性能分析小结和作业课堂练习程序讲解P120,4.21AVL(Adelson-Velskii和Landis)树是带有平带有平衡条件衡条件的二叉查找树。平衡二叉树的定义平衡二叉树的定义一棵AVL(Adelson-Velskii和Landis)树是其每个节点的左子树和右子树的高（深）度最多差1的二叉查找树，即空树的高度定义为-1。hL-hR 10122054820011平衡因子平衡因子=1平衡二叉树平衡二叉树平衡二叉树的定义平衡二叉树的定义52814377281435非平衡二叉树非平衡二叉树平衡二叉树平衡二叉树平衡二叉树的定义平衡二
2、叉树的定义单旋转举例造成不平衡的原因双旋转平衡二叉树的构造平衡二叉树的构造n当向一个AVL树中插入一个新节点是，有可能破坏AVL树的特性。平衡二叉树的构造平衡二叉树的构造n如果发生这种情况，就需在插入完成之前恢复平衡的性质。我们称恢复调整的过程为旋转(rotation)52814376将会破坏关键字为将会破坏关键字为8的节点的节点处的平衡。处的平衡。将将6插入到插入到AVL树中树中即关键字为即关键字为8的节点必须重的节点必须重新平衡。新平衡。n我们把必须重新平衡的节点叫做。由于任意节点最多有两个孩子，因此出现高度不平衡就需要点的两棵子树的高度差2。平衡二叉树的构造平衡二叉树的构造n 造成不平衡
3、的原因有下面几种情况：1.对对的左孩子的左子树进行一次插入。2.对对的左孩子的右子树进行一次插入。3.对对的右孩子的左子树进行一次插入。4.对对的右孩子的右子树进行一次插入。LL型型LR型型RL型型RR型型ABCX2LLABCX2LRABCX-2RRABCX-2RL平衡二叉树的构造平衡二叉树的构造n一、插入发生在“外边”的情况，即LL型和RR型 平衡方案：单旋转(single rotation)平衡二叉树的构造平衡二叉树的构造-平衡方案平衡方案n二、插入发生在“内部”的情况，即LR型和RL型 平衡方案：双旋转(double rotation)ABBLBRARABBLARh-1h-1h-1h-1
4、平衡二叉查找树平衡二叉查找树插入插入x后不再平衡后不再平衡ABBLBRARhh-1X平衡二叉树的构造平衡二叉树的构造-单旋转单旋转n一、单旋转-LL型 12抓住节点抓住节点B往上拽使之成为根节点，自然，往上拽使之成为根节点，自然，A成为了成为了B的的右孩子，右孩子，BL,AR的性质不变，的性质不变，BR成为了成为了A的左孩子。的左孩子。ABBLBRARhh-1XBABRBLhXARh-1n一、单旋转-LL型的调整过程AL平衡二叉树的构造平衡二叉树的构造-单旋转单旋转右旋转右旋转-1AALh-1BRABBLh-1AALh-1-2BRABBLhXn一、单旋转-RR型插入插入x后不再平衡后不再平衡平
5、衡二叉查找树平衡二叉查找树平衡二叉树的构造平衡二叉树的构造-单旋转单旋转AALh-1-2BRABBLhXALh-10BBLABRhXn一、单旋转-RR型的调整过程抓住节点抓住节点B往上拽使之成为根节点，自然，往上拽使之成为根节点，自然，A成为了成为了B的的左孩子，左孩子，BR,AL的性质不变，的性质不变，BL成为了成为了A的右孩子。的右孩子。AL平衡二叉树的构造平衡二叉树的构造-单旋转单旋转左旋转左旋转从空从空AVLAVL树开始依次插入关键字树开始依次插入关键字3,2,1,4,5,6,73,2,1,4,5,6,7321插入插入223插入插入1324LL型，右旋转型，右旋转31插入插入4231插
6、入插入554231RR型，左旋转型，左旋转24153单旋转举例单旋转举例24153插入插入6241536RR型，左旋转型，左旋转465213从空从空AVLAVL树开始依次插入关键字树开始依次插入关键字3,2,1,4,5,6,73,2,1,4,5,6,7单旋转举例单旋转举例465213插入插入77465213RR型，左旋转型，左旋转7564213从空从空AVLAVL树开始依次插入关键字树开始依次插入关键字3,2,1,4,5,6,73,2,1,4,5,6,7单旋转举例单旋转举例h-1BCRABBLARh-1CCLX2平衡二叉树的构造平衡二叉树的构造-双旋转双旋转n一、双旋转-LR型1h-2CRAB
7、BLARh-1CCL插入插入x后不再平衡后不再平衡平衡二叉查找树平衡二叉查找树先在先在A A的左儿子和孙子之间左旋转的左儿子和孙子之间左旋转，再在，再在A A和它的新儿子之间右旋转和它的新儿子之间右旋转CRBLAARh-1CBh-1CLX2h-1CRABBLARh-1CCL2X平衡二叉树的构造平衡二叉树的构造-双旋转双旋转n一、双旋转-LR型的调整过程CRAARh-1Ch-1BBLCLX2ACh-1BBLCLX0CRARh-1平衡二叉树的构造平衡二叉树的构造-双旋转双旋转n一、双旋转-LR型的调整过程先在先在A A的左儿子和孙子之间左旋转的左儿子和孙子之间左旋转，再在再在A A和它的新儿子之间
8、右旋转和它的新儿子之间右旋转-1AALh-1BRABCLCRCh-2Xh-1-2平衡二叉树的构造平衡二叉树的构造-双旋转双旋转n一、双旋转-RL型插入插入x后不再平衡后不再平衡平衡二叉查找树平衡二叉查找树ALh-1BRABCLCRCAALh-1BRABCLCRCXh-1-2ALh-1ABBRCCLCRXh-1-2平衡二叉树的构造平衡二叉树的构造-双旋转双旋转先在先在A A的右儿子和孙子之间右旋转的右儿子和孙子之间右旋转，再在，再在A A和它的新儿子之间左和它的新儿子之间左旋转旋转n一、双旋转-RL型的调整过程AALh-1BRABCLCRCXh-1-2ALh-1CLCABRBCRXh-10平衡二
9、叉树的构造平衡二叉树的构造-双旋转双旋转先在先在A A的右儿子和孙子之间右旋转，的右儿子和孙子之间右旋转，再在再在A A和它的新儿子之间左和它的新儿子之间左旋转旋转n一、双旋转-RL型的调整过程例如例如:依次插入关键字依次插入关键字5,4,2,8,6,95,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转平衡二叉树的构造平衡二叉树的构造举例举例42658942689向左旋转一次继续插入关键字继续插入关键字 9 95平衡二叉树的构造平衡二叉树的构造举例举例平衡二叉树的查找性能分析平衡二叉树的查找性能分析 在平衡树上进行查找的过程和二叉查找树相同，在平衡树上进行查找的过
10、程和二叉查找树相同，因此，因此，查找过程中和给定值进行比较的关键字的个数查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。不超过平衡树的深度。问：含问：含 n n 个关键字个关键字的二叉平衡树的二叉平衡树可能达到的最可能达到的最大深度大深度是多少？是多少？n=0空树空树最大深度为最大深度为0 0n=1最大深度为最大深度为1 1n=2最大深度为最大深度为2 2平衡二叉树的查找性能分析平衡二叉树的查找性能分析n=3?n=4最大深度为最大深度为3 3n=7最大深度为最大深度为 4 4平衡二叉树的查找性能分析平衡二叉树的查找性能分析1.44log(n+2)-1.328n=5,6?反过来问，深
11、度为深度为h h 的二叉平衡树平衡树中所含节点的含节点的最小值最小值N Nh h是多少？h=0N0=0h=1h=2h=3N1=1N2=2N3=4一般情况下，一般情况下，Nh=Nh-1+Nh-2+1利用归纳法可证得，利用归纳法可证得，Nh=Fh+2-1平衡二叉树的查找性能分析平衡二叉树的查找性能分析3）因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和进行比较的关键字的个数和 log(n)log(n)相当。1）由此推得，深度为深度为 h h 的二叉平衡树二叉平衡树中所含含节点的最小值节点的最小值 N Nh h=h+2h+2/5-1/5-12）反之，含有含有 n
12、n 个节点的二叉平衡树能达到个节点的二叉平衡树能达到的最大深度的最大深度 h hn n=log=log(5(n+1)-2 5(n+1)-2 251 平衡二叉树的查找性能分析平衡二叉树的查找性能分析课堂练习课堂练习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=th
13、eElement;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
14、=null?-1:t.height;ABABARXBLARBRBRXBL程序讲解程序讲解-单旋转单旋转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;2100private AvlNode rotateWithLeftChild(AvlNode A)/LL型，右旋转AvlNode B=A.left;A.height=Math.
15、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;程序讲解程序讲解-单旋转单旋转ABABXALBLBRXBRBLALAvlNode 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.h
16、eight)+1;程序讲解程序讲解-单旋转单旋转-2-100private 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;ABAR h-1CR2-1CBL1ABARCRCBLCL0-10CLh-2LR型：先以型：先以C为根左旋转
17、，再以为根左旋转，再以C为根右旋转为根右旋转ABARCRCBLCL022程序讲解程序讲解-双旋转双旋转rotateWithLeftChild(B)rotateWithRightChild(A)rotateWithLeftChild(A.left)(a)ABARh-12-1CBL-1ABARCLCBLCR100CRCLh-2(b)ABARCLCBLCR121程序讲解程序讲解-双旋转双旋转ABAR h-1CR2-1CBLCL0ABARCRCBLCL000(c)ABARCRCBLCL021程序讲解程序讲解-双旋转双旋转private AvlNode doubleWithLeftChild(AvlNo
18、de A)A.left=rotateWithLeftChild(A.left);程序讲解程序讲解-双旋转双旋转return rotateWithRightChild(A);/LR型，先左旋转，后右旋转对于对于RL型，同理可得到型，同理可得到doubleWithRightChild()方法，方法，详见课本详见课本100页，页，4-43private AvlNode insert(AnyType x,AvlNode t)程序讲解程序讲解-主程序主程序if(compareResult0)/插入到右子树else ;/已存在项x，不进行任何处理if(t=null)/空树return new AvlNod
19、e(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);elset=doubleWithLeftChild(t);/需平衡的情况/LL型LR型/原来左子树高，插入到左子树后更高，需要平衡/原来平衡，插入左子树后，则长高/原来左子树低，插入
20、一个节点后左子树长高，则平衡程序讲解程序讲解-主程序主程序/插入到插入到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);elset=doubleWithRightChild(t);/需平衡的情况/RR型RL型/原来右子树高，插入到右子树后更高，需要平衡/原来平衡，插入右子树后，则长高/原来右子树低，插入一个节点后右子树长高，则平衡小结和作业小结和作业平衡二叉树平衡二叉树1.平衡二叉树的定义平衡二叉树的定义 2.如何建立平衡二叉树如何建立平衡二叉树 3.构造平衡二叉树的基本操作构造平衡二叉树的基本操作 4.平衡二叉树查找的性能分析平衡二叉树查找的性能分析 1.LL 2.LR 3.RR4.RL作业：作业：P120,4.19
