一、什么是平衡二叉树搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL
平衡二叉树（BalancedBinaryTree）（AVL树）：空树，或者任一结点左、右子树高度差的绝对值不超过1，即
BF(T)
≤1
“平衡因子（BalanceFactor，简称BF）:BF(T)=hL-hR，其中hL和hR分别为T的左、右子树的高度。
二、平衡二叉树的高度
设nh为高度为h的平衡二叉树的最少结点数。结点数最少时：
三、平衡二叉树的调整
1、右单旋
不平衡的“发现者”是Mar，“麻烦结点”Nov在发现者右子树的右边，因而叫RR插入，需要RR旋转（右单旋）
2、左单旋
“发现者”是Mar，“麻烦结点”Apr在发现者左子树的左边，因而叫LL插入，需要LL旋转（左单旋）
3、左-右双旋
“发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫LR插入，需要LR旋转
4、右-左双旋
“发现者”是Aug，“麻烦结点”Dec在右子树的左边，因而叫RL插入，需要RL旋转
typedefstructAVLNode*Position;typedefPositionAVLTree;/*AVL树类型*/typedefintElementType;structAVLNode{ElementTypeData;/*结点数据*/AVLTreeLeft;/*指向左子树*/AVLTreeRight;/*指向右子树*/intHeight;/*树高*/};intMax(inta,intb);intGetHeight(AVLTreetree);AVLTreeSingleLeftRotation(AVLTreeA);AVLTreeSingleRightRotation(AVLTreeA);AVLTreeDoubleLeftRightRotation(AVLTreeA);AVLTreeDoubleRightLeftRotation(AVLTreeA);AVLTreeInsert(AVLTreeT,ElementTypeX);
#include"Lesson4_2_1.h"#includestdio.h#includeiostreamintMax(inta,intb){returnab?a:b;}intGetHeight(AVLTreetree){if(tree==NULL)return0;returntree-Height;}AVLTreeSingleLeftRotation(AVLTreeA){/*注意：A必须有一个左子结点B*//*将A与B做左单旋，更新A与B的高度，返回新的根结点B*/AVLTreeB=A-Left;A-Left=B-Right;B-Right=A;A-Height=Max(GetHeight(A-Left),GetHeight(A-Right))+1;B-Height=Max(GetHeight(B-Left),A-Height)+1;returnB;}AVLTreeSingleRightRotation(AVLTreeA){/*注意：A必须有一个右子结点B*//*将A与B做左单旋，更新A与B的高度，返回新的根结点B*/AVLTreeB=A-Right;A-Right=B-Left;B-Left=A;A-Height=Max(GetHeight(A-Left),GetHeight(A-Right))+1;B-Height=Max(GetHeight(B-Right),A-Height)+1;returnB;}AVLTreeDoubleLeftRightRotation(AVLTreeA){/*注意：A必须有一个左子结点B，且B必须有一个右子结点C*//*将A、B与C做两次单旋，返回新的根结点C*//*将B与C做右单旋，C被返回*/A-Left=SingleRightRotation(A-Left);/*将A与C做左单旋，C被返回*/returnSingleLeftRotation(A);}AVLTreeDoubleRightLeftRotation(AVLTreeA){/*注意：A必须有一个左子结点B，且B必须有一个右子结点C*//*将A、B与C做两次单旋，返回新的根结点C*//*将B与C做右单旋，C被返回*/A-Right=SingleLeftRotation(A-Right);/*将A与C做左单旋，C被返回*/returnSingleRightRotation(A);}AVLTreeInsert(AVLTreeT,ElementTypeX){/*将X插入AVL树T中，并且返回调整后的AVL树*/if(!T){/*若插入空树，则新建包含一个结点的树*/T=(AVLTree)malloc(sizeof(structAVLNode));T-Data=X;T-Height=0;T-Left=T-Right=NULL;}/*if(插入空树)结束*/elseif(XT-Data){/*插入T的左子树*/T-Left=Insert(T-Left,X);/*如果需要左旋*/if(GetHeight(T-Left)-GetHeight(T-Right)==2)if(XT-Left-Data)T=SingleLeftRotation(T);/*左单旋*/elseT=DoubleLeftRightRotation(T);/*左-右双旋*/}/*elseif(插入左子树)结束*/elseif(XT-Data){/*插入T的右子树*/T-Right=Insert(T-Right,X);/*如果需要右旋*/if(GetHeight(T-Left)-GetHeight(T-Right)==-2)if(XT-Right-Data)T=SingleRightRotation(T);/*右单旋*/elseT=DoubleRightLeftRotation(T);/*右-左双旋*/}/*elseif(插入右子树)结束*//*elseX==T-Data，无须插入*//*别忘了更新树高*/T-Height=Max(GetHeight(T-Left),GetHeight(T-Right))+1;returnT;}预览时标签不可点收录于话题#个上一篇下一篇