第四章：树与二叉树（平衡二叉树）

1.平衡二叉树

平衡二叉树：AVL,任意结点的平衡因子的绝对值不超过一。

平衡因子：左子树高度 - 右子树高度

如上图二叉树，是否是平衡二叉树？

可以把所有结点的平衡因子计算出来，进行判断，可以看出此二叉树是平衡二叉树。

高度为h的最小(结点数最少)平衡二叉树的结点数Nh?

根据平衡二叉树 右侧那个结点的值可以选择：h、h-1和h-2，如果选择h，加上根节点1层，总层数为h+1，不符合题意。其中h-1和h-2都可以选择但是为什么选择h-2？是因为这里说的是最小平衡二叉树，h-1层结点数肯定比h-2层结点数多。N0=0（0层结点数为0）N1=1（结点数为1）

比如我们现在要计算高度为3的最小平衡二叉树的结点数。则：

N3=N2+N1+1; =》N2=N1+N0+1=2; =》N3=2+1+1=4;

1.1平衡二叉树的判断

利用递归的后序遍历过程:

• 判断左子树是一棵平衡二叉树
• 判断右子树是一棵平衡二叉树
• 判断以该结点为根的二叉树为平衡二叉树 判断条件 若左子树和右子树均为平衡二叉树且左子树与右子树高度差的绝对值小于等于1,则平衡。

根据判断条件我们知道，每个结点要保存两个变量：一个是该节点的平衡性(b:1平衡 0不平衡)另一个是该节点的高度(h)。

//参1 该棵树的根节点void Judge_AVL(BiTree bt,int &balance,int &h){ //左子树平衡性左子树高度 右子树平衡性右子树高度 int bl=0,br=0,hl=0,hr=0; if(bt==NULL){//如果根节点为空 h=0; //高度设为0 balance=1; //并且是平衡的 }else if(bt->lchild==NULL&&bt->rchild==NULL){ //左子树和右子树都为空 h=1; //高度为1 balance=1; //平衡的 }else{ Judge_AVL(bt->lchild,bl,hl); //判断左子树 Judge_AVL(bt->rchild,br,hr); //判断右子树 //下面计算该节点为根二叉树的高度 //首先判断哪个子树的高度高，然后加1即可 if(hl>hr){ h=hl+1; }else{ h=hr+1; } //判断平衡性 // abs 是取绝对值 if(abs(hl-hr)<2&&bl==1&&br==1){ balance=1; }else{ balance=0; } }}

2.平衡二叉树的插入

平衡二叉树的插入过程其实和二叉排序树的插入过程相比多了一步，如果按照二叉排序树的插入过程，所形成的二叉树不一定是平衡二叉树，所以我们需要先插入之后进行调整。即：先插入后调整。

调整原则：每次调整最小不平衡子树

例如，如上图插入完成之后我们需要调整，我们调整是从插入结点开始，向上依次调整。首先4结点平衡因子为-1，符合平衡二叉树，然后向上6结点平衡因子为2，不符合平衡二叉树，则需要调整。

2.1LL平衡旋转(右单旋转)

出现不平衡的原因：在结点A的左孩子的左子树上插入了新结点。

调整方法：右旋操作：用A的左孩子B代替A，将A结点称为B的右子树根结点，而B的原右子树则作为A的左子树。

出现了不平衡的情况，下面调整成平衡二叉树：

2.2RR平衡旋转(左单旋转)

出现不平衡的原因：在结点A的右孩子的左子树上插入了新结点。

调整方法：左旋操作：用A的右孩子B代替A，将A结点称为B的左子树根结点，而B的原左子树则作为A的右子树。

2.2LR平衡旋转(先左后右双旋转)

出现不平衡的原因：在结点A的左孩子的右子树上插入了新结点。

调整方法：先左旋后右旋转操作：将A的左孩子B的右孩子结点C代替B，然后再将C结点向上代替A的位置。

注意：其中Cl和Cr也可能都为空，因为B的右子树Br可能为空。

2.2RL平衡旋转(先右后左双旋转)

出现不平衡的原因：在结点A的左孩子的左子树上插入了新结点。

调整方法：先右旋后左旋转操作：将A的右孩子B的左孩子结点C代替B，然后再将C结点向上代替A的位置。