平衡二叉树（AVLTREE）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 前言
• 一、pandas是什么？
• 二、使用步骤
  • 1.引入库
  • 2.读入数据
• 总结

          二叉搜索树的查找、插入、删除性能的时间复杂度均为Ologn但这是在期望的前提下，在最好和最坏的前提下差别较大。在最好情况下，二叉查找树的形态和二分查找的判定相似，每次可以缩小一半的查找范围。但是在最坏的情况下，二叉查找树为单支树，即只有从左子树到右子树，每次查找的搜索范围为n-1，退化为顺序查找。

二叉查找树的效率和树高成反比，那么为了提高二叉查找树的效率这里就引入了平衡二叉树。

平衡二叉查找树即平衡二叉树具有以下性质：

       1：平衡二叉树可以为空树。

       2：左右子树的高度差值的绝对值不超过1.

       3：左右子树也是平衡二叉树。

平衡二叉树就是进阶版的二叉搜索树，就是在二叉搜索树每次插入节点的时候进行判断，是否进行调整。下面就来构建一个平衡二叉树。

typedef struct AVLNode
{
	int data;
	int height;//相比于二叉搜索树多了一个height 这是用来判断是否平衡的因子。
	AVLNode* lchild;
	AVLNode* rchild;
}*AVLTree;

int Height(AVLTree& T)//返回树高
{
	return T->height;
}

void updataHeight(AVLTree & T)
{
	T->height = max(Height(T->lchild), Height(T->rchild)) + 1;//双亲的树高永远比左右子树的树高的最大值高一
}

判断是否平衡方法：传入双亲节点 判断该节点的左右节点的高度差的绝对值是否>1；

由于是递归调用所以由插入节点向上判断是否平衡

首先AVLTREE的调整分为四种：

1：LL型：

              插入节点的位置在不平衡节点的左子树的左子树。

AVLTree LL_Rotation(AVLTree& T)
{
	AVLTree temp = T->lchild;
	T->lchild = temp->rchild;
	temp->rchild = T;
	updataHeight(T);
	updataHeight(temp);
	return temp;
}

2：RR型：

                 插入节点的位置在不平衡节点的右子树的右子树。

AVLTree RR_Rotation(AVLTree& T)
{
	AVLTree temp = T->rchild;
	T->rchild = temp->lchild;
	temp->lchild = T;
	updataHeight(T);
	updataHeight(temp);
	return temp;
}

3：RL型：

AVLTree RL_Rotation(AVLTree &T)
{
	T->rchild = LL_Rotation(T->rchild);
	return RR_Rotation(T);
}

4：LR型：

AVLTree LR_Rotation(AVLTree& T)
{
	T->lchild = RR_Rotation(T->lchild);
	return LL_Rotation(T);
}

AVLTree Insert(AVLTree& T, int data)
{
	if (T == NULL)//找到了插入位置
	{
		AVLTree S = new AVLNode;
		S->data = data;
		S->height = 1;
		S->lchild = S->rchild = NULL;
		T = S;
		return T;
	}
	if (T->data == data) return T;//原来已经存在，不做操作。
	else if (T->data > data)
	{
		T->lchild = Insert(T->lchild, data);//递归插入
		if (Height(T->lchild) - Height(T->rchild) == 2)//从左子树插入只有可能左比右高破坏平衡。
		{
			if (data > T->lchild->data)//判断哪一种类型
			{
				T = LR_Rotation(T);//LR型
			}
			else
			{
				T = LL_Rotation(T);//LL型
			}
		}
	}
	else
	{
		T->rchild = Insert(T->rchild, data);//递归插入
		if (Height(T->rchild) - Height(T->lchild) == 2)//从右子树插入只有可能右比左高破坏平衡。
		{
			if (data > T->rchild->data)//判断哪一种类型
			{
				T = RR_Rotation(T);//LR型
			}
			else
			{
				T = RL_Rotation(T);//LL型
			}
		}
	}
	updataHeight(T);
	return T;
}

            我们知道二叉搜索树的删除分为四种情况，但是接下来的代码我只将其分为了两种情况。

1待删除节点没有右子树。直接将其删除并且连接该节点的左子树即可。

2待删除节点含有右子树节点。我们知道二叉搜索树的·待删除节点如果同时含有左右子树的话有两种替换方式，这里我们就用待删除节点的右子树的最左节点来替换。这里的话我们可以不考虑该节点是否含有左子树（读者可以自己建立一个简单的AVLTREE来实验一下）。

代码如下：

void Adjust(AVLTree& T)//判断该节点是否平衡。
{
	if (T == NULL)//不平衡无非俩种情况，左比右高2，右比左高2
		return;
	if (Height(T->lchild) - Height(T->rchild) == 2)//第一种左比右，既然左比右高观察左子树的左右子树看看是那种类型
	{
		if (Height(T->lchild->lchild) >= Height(T->lchild->rchild))//LL型
			LL_Rotation(T);
		else
			LR_Rotation(T);
	}
	if (Height(T->rchild) - Height(T->lchild) == 2)//这里同理
	{
		if (Height(T->rchild->lchild) >= Height(T->rchild->rchild))
			RL_Rotation(T);
		else
			RR_Rotation(T);
	}
	updataHeight(T);//更新树高
}
AVLTree Delete(AVLTree& T,int data)
{
	if (T == NULL)
	{
		return T;
	}
	if (T->data == data)//如果找到节点进行操作
	{
		if (T->rchild == NULL)//第一种情况，右子树为空
		{
			AVLTree temp = T;
			T = T->lchild;
			delete temp;
		}
		else//另外一种情况
		{
			AVLTree temp = T ->rchild;
			while (temp ->lchild)//循环寻找右子树的最左节点
			{
				temp = temp->lchild;
			}
			T->data = temp->data;//替换
			T ->rchild = Delete(T->rchild, T->data);//删除上方找到的节点
			updataHeight(T);
		}
	}
	else if (T->data > data)
	{
		T->lchild = Delete(T->lchild, data);
	}
	else
	{
		T->rchild = Delete(T->rchild, data);
	}
	updataHeight(T);
	Adjust(T);//判断该节点是否平衡
	return T;
}

以上就是AVLTREE的基本实现方法。

由于作者能力有限，无法作图来进行更好的演示。

谢谢。