本文共 4090 字，大约阅读时间需要 13 分钟。

平衡二叉树：是一种二叉排序树（BST Tree），其中每一个结点的左子树和右子树的高度差最多等于1。将二叉树上结点的左子树深度减去右子树的深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只能是-1,0,1。

平衡二叉树的实现原理

平衡二叉树构建的基本思想就在在构建二叉排序树的过程中，每当成功插入一个结点后，DFS自下而上递归检查每个子树（从以插入结点的父结点为根的子树开始）寻找最小不平衡子树，一旦找到马上将其消灭，消灭后把*taller置为false，表示本次由于新结点插入引起的调整已经完成；若新插入的结点没有破坏树的平衡性，则直接把以插入结点的父结点为根的子树的(*T)->bf置为EH,并把*taller置为false即可。

旋转图解

左旋操作

左旋就是让结点A的右孩子的左子树（即结点B的左子树）成为结点A的右子树，再将A改成B的左子树，最后将结点B替换结点A成为根结点。（左旋函数对传入子树的根结点进行了替换，涉及到了结点地址的改变，所以要用二重指针做函数形参！）

右旋操作

右旋就是让结点A的左孩子的右子树（即结点B的右子树）成为结点A的左子树，再将A改成B的右子树，最后将结点B替换结点A成为根结点。

双旋操作

左平衡情况(分情况讨论)：未插入新结点前的平衡二叉树原本就是T的左边高，然后新插入的结点又在T的左子树上，因此需要调用左平衡函数重新使其平衡。

右平衡情况(分情况讨论)：未插入新结点前的平衡二叉树原本就是T的右边高，然后新插入的结点又在T的右子树上，因此需要调用右平衡函数重新使其平衡。

新结点的插入以及新结点插入后自下而上重新把整棵树调整平衡（DFS）：

新结点成功插入后，自下而上对每个子树进行判断。直到找到这样一个子树，若经过相应处理后(*T)->bf为EH，则把*taller置为false,说明本次插入后的调整已经完成，现有的整棵大树又回到了平衡状态。

完全理解算法后，完整的代码如下：

#include
   
    using namespace std;typedef struct BiTNode{   	int data;	int bf;	struct BiTNode* lchild, *rchild;}BiTNode;//左旋转void L_Rotate(BiTNode**T)//T是一个二重指针{   	BiTNode* R = (*T)->rchild;	(*T)->rchild = R->lchild;	R->lchild = *T;	*T = R;}//右旋转void R_Rotate(BiTNode**T){   	BiTNode* L = (*T)->lchild;	(*T)->lchild = L->rchild;	L->rchild = *T;	*T = L;}#define LH +1 //左高#define EH  0 //等高#define RH -1 //右高//T的左边高，不平衡，要调用左平衡函数使其平衡void LeftBalance(BiTNode**T){   	BiTNode*L, *Lr;	L = (*T)->lchild;	Lr = L->rchild;	switch (L->bf)	{   	case LH:		L->bf = (*T)->bf = EH;		R_Rotate(T);		break;	case RH:		switch (Lr->bf)		{   		case LH:			L->bf = EH;			(*T)->bf = RH;			break;		case EH:			L->bf = (*T)->bf = EH;			break;		case RH:			L->bf = LH;			(*T)->bf = EH;			break;		}		Lr->bf = EH;		L_Rotate(&L);//注意这两句！		(*T)->lchild = L;//注意！		R_Rotate(T);		break;	}}//T的右边高，不平衡，要调用右平衡函数使其平衡void RightBalance(BiTNode**T){   	BiTNode*R, *Rl;	R = (*T)->rchild;	Rl = R->lchild;	switch (R->bf)	{   	case RH:		R->bf = (*T)->bf = EH;		L_Rotate(T);		break;	case LH:		switch (Rl->bf)		{   		case LH:			R->bf = RH;			(*T)->bf = EH;			break;		case EH:			R->bf = (*T)->bf = EH;			break;		case RH:			R->bf = EH;			(*T)->bf = LH;			break;		}		Rl->bf = EH;		R_Rotate(&R);//注意这两句！		(*T)->rchild = R;//注意！		L_Rotate(T);		break;	}}//往平衡二叉树上插入结点bool InsertAVL(BiTNode**T, int data, bool *taller){   	if (*T == NULL) //插入新结点，*taller置为true，结束递归	{   		*T = new BiTNode;		(*T)->bf = EH;		(*T)->rchild = (*T)->lchild = NULL;		(*T)->data = data;		*taller = true;//*taller为true表示由于新结点的插入可能会产生不平衡子树，需要进行调整					   //*taller为false表示经过调整后，新的树仍然保持平衡	}	else	{   		if (data == (*T)->data)  //树中有相同数据的结点，插入失败，结束递归		{   			*taller = false;			return false;		}		if (data < (*T)->data)   //往左子树中进行搜索		{   			if (!InsertAVL(&(*T)->lchild, data, taller))   //左子树中有相同数据的结点，插入失败，结束递归			{   				*taller = false;				return false;			}			if (*taller)//InsertAVL(&(*T)->lchild的结果为true，说明该结点已经被插入左子树，所以需要自下而上（从以插入结点的父结点为根的子树开始）寻找最小不平衡子树，若找到了最小不平衡子树，则对其进行调整，调整完毕后再把*taller置为false，表示新的大树再次平衡			{   				switch ((*T)->bf) //分情况讨论				{   				case LH://说明插入前T的左边子树更高，需要左平衡处理					LeftBalance(T);					*taller = false;					break;				case EH://说明插入前T的左右子树等高，插入后左边子树更高					(*T)->bf = LH;					*taller = true;					break;				case RH://说明插入前T的右边子树更高，插入后左右子树等高					(*T)->bf = EH;					*taller = false;					break;				}			}		}		else                     //往右子树进行搜索		{   			if (!InsertAVL(&(*T)->rchild, data, taller))			{   				*taller = false;				return false;			}			if (*taller)			{   				switch ((*T)->bf)				{   				case LH:					(*T)->bf = EH;					*taller = false;					break;				case EH:					(*T)->bf = RH;					*taller = true;					break;				case RH:					RightBalance(T);					*taller = false;					break;				}			}		}	}	return true;//说明插入结点成功}int main() {   	int a[10] = {    3,2,1,4,5,6,7,10,9,8 };	bool taller = false;	BiTNode* T = NULL;//根结点	for (int i = 0; i < 10; i++) {   		InsertAVL(&T, a[i], &taller);	}	cout << T->data << endl;	cout << T->lchild->data << " " << T->rchild->data << endl;	cout << T->lchild->lchild->data << " " << T->lchild->rchild->data << " " << T->rchild->lchild->data << " " << T->rchild->rchild->data << endl;	system("pause");	return 0;}