《大话数据结构》C++实现二叉平衡树的建立

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉排序树。

高度差可以用平衡因子bf来定义，我们用左子树的高度减去右子树的高度来表示bf，即-1<|bf|<1。

引入平衡二叉树是由于二叉排序树，在某些情况会导致树的高度一直的增加，比如一组有序的数据，在查找或创建时递归层级会很深，导致方法栈容易溢出。

平衡二叉树是通过旋转来缓解树高度增加过快的情况。

先介绍下最小不平衡节点的概念：插入一个节点之后，距离这个插入节点最近的不平衡节点就是最小不平衡节点。就是说在递归插入节点后，开始回溯，碰到的第一个不平衡的节点就是最小不平衡节点。

当最小不平衡节点右子树高则需要左旋，左子树高则需要右旋（还有些情况需要先对其左/右子树旋转）。

思考：

1、既然旋转是通过平衡因子|bf|>1来决定怎么旋转的，那么在旋转前这些平衡因子是什么时候赋值的呢？

2、旋转之后，哪些节点需要调整？，平衡因子又改如何调整呢？

下图只列出左子树高的几种情况，T表示最小不平衡节点，L表示其左子树，LR表示L的右子树，

为了形象用EH(0)，LH(1)，RH(-1)分别表示某一节点 左右子树相等、左子树高、右子树高三种情况。

根据L节点的左右子树高度差来确定直接右旋还是先左旋再右旋，因为L为最小不平衡子树的左子树，故不会出现L.bf=EH的情况。

一、L.bf=LH

右旋：

旋转之后T.bf=L.bf=EH

二、L.bf=RH

先左旋再右旋：

当L的平衡因子为-1时则需要先对L进行右旋，然后再对T进行左旋。根据LR的情况再分为下面三种（因为旋转两次，那么最后最小不平衡子树的根节点为LR，并且LR.bf=EH）

1、 LR=EH

旋转之后T.bf=L.bf=EH

2、 LR=LH

旋转之后T.bf=RH, L.bf=EH

3、 LR=RH

旋转之后T.bf=EH, L.bf=LH

代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

typedef int Status;

constexpr auto LH = +1;
constexpr auto EH = 0;
constexpr auto RH = -1;


//定义平衡二叉树的节点结构(在二叉排序树中加入一个bf来存储平衡因子)
typedef struct BiTNode
{
	int data;
	int bf;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;


void R_Rotate(BiTree* p);
void L_Rotate(BiTree* p);
void LeftBalance(BiTree *T);
void RightBalance(BiTree* T);
void InOrderTraverse(BiTree *T);
Status InsertAVL(BiTree *T,int e,Status *taller);


//进行二叉平衡树时的右旋操作
void R_Rotate(BiTree *p)
{
	BiTree L;
	L = (*p)->lchild;
	(*p)->lchild = L->rchild;
	L->rchild = *p;
	*p = L;
}


//进行二叉平衡树时的左旋操作
void L_Rotate(BiTree *p)
{
	BiTree R;
	R = (*p)->rchild;
	(*p)->rchild = R->lchild;
	R->lchild = (*p);
	*p = R;
}

//构建二叉平衡树时左边太“重”，进行左平衡处理函数
void LeftBalance(BiTree* T)
{
	BiTree L, Lr;
	L = (*T)->lchild;
	switch (L->bf)
	{/*检查T的左子树的平衡度，并做相应的处理*/
	case LH:/*新节点插入在了T的左孩子的左子树上，只要做单左旋处理*/
		(*T)->bf = L->bf = EH;
		R_Rotate(T);
		break;
	case RH:/*新节点插入在了T的左孩子的右子树上，要做双旋处理，
			通过判断T的左孩子的右子树的根节点的bf来决定进行双旋处理后各自的bf值*/
		Lr = L->rchild;
		switch (Lr->bf)
		{
		case LH:
			(*T)->bf = RH;
			L->bf = EH;
			break;
		case EH:
			(*T)->bf = L->bf = EH;
			break;
		case RH:
			(*T)->bf = EH;
			L->bf = LH;
			break;
		}
		Lr->bf = EH;
		L_Rotate(&(*T)->lchild);
		R_Rotate(T);
	}
}

//构建二叉平衡树时右边太“重”，进行右平衡处理函数
void RightBalance(BiTree* T)
{
	BiTree R, Rl;
	R = (*T)->rchild;
	switch (R->bf)
	{/*检查T的右子树的平衡度，并做相应的处理*/
	case RH:/*新节点插入在了T的右孩子的右子树上，只要做单左旋处理*/
		(*T)->bf = R->bf = EH;
		L_Rotate(T);
		break;
	case LH:/*新节点插入在了T的右孩子的左子树上，要做双旋处理，
			通过判断T的右孩子的左子树的根节点的bf来决定进行双旋处理后各自的bf值*/
		Rl = R->lchild;
		switch (Rl->bf)
		{
		case LH:
			(*T)->bf = EH;
			R->bf = RH;
			break;
		case EH:
			(*T)->bf = R->bf = EH;
			break;
		case RH:
			(*T)->bf = LH;
			R->bf = EH;
			break;
		}
		Rl->bf = EH;
		R_Rotate(&(*T)->rchild);
		L_Rotate(T);
	}
}




//构建二叉平衡树函数
Status InsertAVL(BiTree* T, int e, Status* taller)
{
	if (!*T)
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->bf = EH;
		(*T)->lchild = (*T)->rchild = NULL;
		*taller = true;
	}
	else
	{
		if (e==(*T)->data)
		{
			*taller = false;
			return false;
		}
		if (e<(*T)->data)
		{
			int result = InsertAVL(&(*T)->lchild,e,taller);
			if (!result)
			{
				return false;
			}
			if (*taller)
			{
				switch ((*T)->bf)
				{
				case LH:
					LeftBalance(T);
					*taller = false;
					break;
				case EH:
					(*T)->bf = LH;
					*taller = true;
					break;
				case RH:
					(*T)->bf = EH;
					*taller = false;
					break;
				}
			}
		}
		else
		{
			int result = InsertAVL(&(*T)->rchild, e, taller);
			if (!result)
			{
				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;
}


//二叉树中序遍历递归算法
void InOrderTraverse(BiTree* T)
{
	if (*T==NULL)
	{
		return;
	}
	InOrderTraverse(&(*T)->lchild);
	cout << (*T)->data << " ";
	InOrderTraverse(&(*T)->rchild);
}

int main()
{
	int i;
	int a[10] = {3,2,1,4,5,6,7,10,9,8};
	BiTree T = NULL;
	Status Numtaller;
	for ( i = 0; i < 10; i++)
	{
		InsertAVL(&T,a[i],&Numtaller);
	}
	//中序遍历输出结果
	InOrderTraverse(&T);
}

本文参考链接：https://link.zhihu.com/?target=https%3A//www.cnblogs.com/zuochengsi-9/p/8660871.html