平衡二叉树详解

《平衡二叉树详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态查找树之平衡二叉树（BalancedBinaryTree，AVL树一、平衡二叉树的概念       平衡二叉树(Balancedbinarytree)是由阿德尔森-维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。定义：平衡二叉树或为空树,或为如下性质的二叉排序树:  （1）左右子树深度之差的绝对值不超过1;  （2）左右子树仍然为平衡二叉树.      平衡因子BF=左子树深度－右子树深度.平衡二叉树每个结点的平衡因子只能是1，0，-

2、1。若其绝对值超过1，则该二叉排序树就是不平衡的。如图所示为平衡树和非平衡树示意图：二、平衡二叉树算法思想若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。        失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示

3、失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。 （1）LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。（2）RR型平衡旋转法由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为

4、C的左子树的根结点。而原来C的左子树则变成A的右子树。（3）LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。        如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。（4）RL型平衡旋转法 

5、 由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。 如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意

6、的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf==2或者 bf==-2的节点。三、二叉排序数的操作及C语言描述     插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有

7、可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。四、二叉排序数的C语言实现#include"stdio.h"#include"stdlib.h"#include"string.h"#defineLH+1 //左高#defineEH0  //等高 #defineRH-1 //右高#defineTRUE1#defineFALSE1#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineL

8、Q(a,b)((a)<=(b))#defineBT(a,b)((a)>(b))typedefintKeyType;typedefintinfo;typedefintBoolean;typedefstructElemType{KeyTypekey;//infootherinfo;};typedefstructBSTNode {  ElemTypedata;  intbf;  BSTNode*lchild,*rchild;//左右孩子指针 }BSTNode,*BSTree