【数据结构】树-平衡二叉树的调整（RR,LL,LR,RL）新增代码实现

时间  2021-01-21

平衡二叉树是一种特殊的二叉排序树，其定义：为空树或者
它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1
在这里插入图片描述
如图，第三个就是错的，因为7的右子树高度为0，左子树高为2，BF（T）= 2不满足要求

在这里插入图片描述
h=3、4、5类似，谨记：树的左右子树依然是平衡二叉树

在这里插入图片描述
通过推算能得出：当一个结点数量为N组成的平衡二叉树，其高度能达到logn

平衡二叉树的调整：

RR旋转
在这里插入图片描述
对于Mar,May组成的二叉树，然后准备插入Nov，如果其插入May的子树上，那么这就无法构成一个平衡二叉树。
是由于Nov连上了May，导致Mar（发现者）的高度差不满足平衡二叉树的定义，因而Nov（麻烦结点）破坏了树的结构，若想平衡起来，很自然想到组成一个头结点，再一个左右子树就满足需求了，于是可以通过对原树进行一次右单旋，变成右边的结构。

抽象化说明：
在这里插入图片描述
对于一个已经平衡的二叉树（图①），在BR位置插入一个节点，变成图②所示，导致这棵树变得不平衡，“麻烦结点”是新节点，“发现者”是A，位置在A右子树的右边，因此进行RR旋转，物理上是将其单旋一次，变成图③的模样。
（别忘了，这也是一个查找树。视频并未提及平衡二叉树和查找树的关系，但请记住，平衡二叉树是一种特殊的二叉排序树）对于BL，由于B是A的右子树，因此BL和BR元素值肯定大于A，因此可以放到A的右子树上。
在这里插入图片描述
这也是RR旋转，依然满足“破坏者”在“发现者”右子树（10）的右边（14）

LL旋转
在这里插入图片描述
插入Apr，导致Mar,May不平衡，此时，作为距离Apr最近的点为“发现者”，在发现者-问题节点之间进行左旋，由于这次Apr是在Mar左子树的左边，因此称为LL旋转
在这里插入图片描述
抽象化说明：类似RR旋转，不多赘述。
对于BR，B是A的左子树，所以BR肯定小于A，因此在旋转后可以放到A的左子树
在这里插入图片描述
接着插入Jan。根据查找树的规则，Jan在Mar的左子树上，这样导致May的平衡被破坏。
此时Jan在May左子树的右子树上，因此这被称为LR旋转。
LR旋转所注意的关键点为May（被破坏点）~Aug ~Mar这三个节点（顺序为破坏者，破坏者的L，破坏者的LR），把这三个节点调平衡了也就调整完毕。
在这里插入图片描述
要做成这样，显然头结点是需要这三个节点的中间值，在题目中就是Mar了。然后左边为比它小的（Aug），右边比它大（May），这样就能变成一个平衡二叉树（如图②）
在这里插入图片描述
抽象概述：
在CL或者CR中新增一个节点，导致A不平衡（不平衡点在A的左子树的右子树，即LR），因此需要在ABC（即A，AL，ALR）这三个点进行LR旋转。
这样还多出CL和CR，由于B<C,A>C,且CL＜C，CR>C能得出：CL肯定比B大，CR肯定比A要小，因此CL连到B的右子树，CR连到B的左子树上，即图③。

RL旋转：
在这里插入图片描述
破坏者（Feb）是在被破坏者（Aug）的右子树的左子树上，因而进行旋转称为RL旋转
过程与LR旋转类似，不多赘述。

继续插入：
在这里插入图片描述
插入June，Mar被破坏，因而需要对Mar，MarL(Dec)，MarLR(Jan)进行调整，也就是LR旋转
在这里插入图片描述
接着插入Oct，显然，RR旋转
在这里插入图片描述
至此为RR,LL,LR,RL旋转的基本概念

2019年4月10日新增代码实现：
要构建一个平衡二叉树，最难的就是在每次插入数据后所需要进行的判断LL，LR，RR，RL旋转
AVL树的定义：其内部必须得有一个“height”来监控每一个节点的子树高度差是否违反要求，用链表为存储结构，其定义如下：

typedef struct AVLNode *AVLTree;
struct AVLNode{
	int value;
	AVLTree left,right;
	int height;
};

链表的创建：正常操作，代码下文一并附上
节点的插入：谨记平衡二叉树的定义：它是一种特殊的二叉搜索树，其左右子树的高度差不超过1，因此在初步插入节点时它的代码结构和二叉搜索树的插入相同：

AVLTree Insert(AVLTree T,int a){
	if(!T){//T为可插入的空节点 
		T = new AVLNode();
		T->value = a;
		T->left = T->right = NULL;
		T->flag = 0;
	}else{
		if(a>T->value)	T->right = Insert(T->right,a);
		else if(a<T->value)	T->left = Insert(T->left,a);
	}
	return T;
}

拿其中一个插入为例，在T->right处插入数据，根据递归会一直到能够插入节点的那个地方然后创建节点，再返回。成功插入后需要逐层返回判断：①此时是否有节点的高度差不满足，即高度差为2的那个节点；②如果满足，应该更新这个节点的高度差。根据自底向上的顺序，肯定会先有正常更新节点的节点，再会有异常高度差节点，因此先解决如何更新高度差：

在这里插入图片描述
注：12345均为结点名，方便表述，并不是值
我们规定，④为新插入的节点，并且深度差为左减右

对于④，很容易明白，其height为0
然后递归返回到③，显然③的深度是1（肉眼观察）。在操作上，这时候③的深度是③的左子树和右子树之差，即T->left和right之差，显然这是1 - 0 = 1，因此标为1，但是在数据上，③的左子树的height为0，③的右子树为空，因此③深度的计算应该是0 - x = 1，很好得出x = -1，因此可以规定：如果子树为空，那么它的height = -1
递归返回到②，根据上述结论，②的深度是 1 - (-1) = 2，需要进行旋转操作。
先不要考虑旋转操作，我们再举个例子。
在这里插入图片描述
同样照搬之前的规定，⑤为新插入节点，height = 0
④的深度应该为 -1 - 0 = -1
③的深度应该为 -1 - (-1) = 0，这样就出问题了，如果在左插入右插入时规定的作差方法还不一样，这样代码实现起来会复杂很多很多，因此这里有一个新思路，我们规定深度都为正数，这样④的深度为1，在③中的操作也就是-1 - 1 = -2，绝对值一下就知道这个深度大于1，虽然-2依然是负数，但这个是会立即进行操作的，在“判断旋转类型”中马上会提及到，不用担心。

那么对于这更新深度的总结：
①如果这个树是叶节点，那么深度就为0
②如果子树为空，其深度（在计算上）应该为-1
③树枝节点的值应该保证其一直为正数，方便接下来的操作
因此，首先，我们需要一个函数GetHeight()来获取其深度

int GetHeight(AVLTree T){
	if(!T)	return -1;
	return T->height;
}

再考虑左减右为负数的情况下，我们要令它的深度保持一个正数，在所有能够正常返回的深度中，配对的有 -1 - 0 =1;1 - 0 = 1; 0 - (-1) = 1; (1 - 1 = 0这种形式不会出现)，可以选用其中的最大值进行+1，也能得到我们想要的深度（这一块我解释的不是太好，希望有大佬能帮忙补充）

T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;

回到上文：如何判断这个是RR还是LL还是RL、LR类型的旋转呢？

判断旋转类型：
由于最初我们规定的深度差是左减右，根据异常值2或者-2能看出，这是左子树太重，出了问题，因而至少能知道这个是L_旋转。在这里再回顾一下LL和LR的定义：LL发生在左子树的左子树，LR发生在左子树的右子树，这个异常节点肯定要么在其发现者左子树的右子树或者左子树，也就是判断异常节点和发现节点左子树的大小关系，如果大，那么就是LR旋转，如果小，那么就是LL旋转，反之对于RR，RL是相同的道理。

if(!T){
		T = new AVLNode();
		T->value = a;
		T->left = T->right = NULL;
		T->height = 0;
	}
	else if(a > T->value){
		T->right = Insert(T->right,a);
		if(GetHeight(T->left) - GetHeight(T->right) == -2){//右子树更重,因此是R_旋转 
			if(a > T->right->value)	T = RR_Rotation(T);//a比右子树更大,即a所放置的地方在右边,因此执行RR旋转 
			else	T = RL_Rotation(T);//反之,a所放置的地方在左子树的左边,因此执行RL旋转,下同 
		}
	}else if(a < T->value){
		T->left = Insert(T->left,a);
		if(GetHeight(T->left) - GetHeight(T->right) == 2){
			if(a < T->left->value)	T = LL_Rotation(T);
			else	T = LR_Rotation(T);
		}
	}

接下来就是对旋转操作的代码实现：
对RR旋转为例：
在这里插入图片描述
A是发现者，因此是以A节点为起点进行操作（其它旋转都是以发现者为起点进行操作），不难看出是把BL连上了A的右儿子，A本身连上了A的左儿子（没错就是那么简单粗暴），重新连接完毕后不要忘了更新节点的深度

AVLTree RR_Rotation(AVLTree T){
	AVLTree AVT = T->right;
	T->right = AVT->left;
	AVT->left = T;
	T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
	AVT->height = Max(GetHeight(AVT->left), T->height) + 1;
	return AVT;
}

对于RL以及LR旋转，以RL为例：
在这里插入图片描述
不难看出，是将C变为头结点，CL变为A的右儿子，CR变为B的左儿子，直接根据所说的进行操作也可以，这里提供浙大数据结构所提供的代码思路：
以先序遍历为准，最初的顺序为ABC，后来变成了CAB，可以看成C一步一步往右挪动，变成根节点。
那么我们可以对BC先进行旋转，C是B的左子树，因此进行一次LL旋转，可以粗糙理解为C和B换了一个位置，此时顺序为ACB，再对AC进行旋转，此时C是A的右子树，因此进行一次RR旋转，这样也能得到想要的结果。
也就是说，RL旋转 = LL旋转 + RR旋转（顺序是反的！）

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

LL和LR旋转代码及思路类似。
最后附上所有代码，根据Root of AVL Tree改写而来：

#include<bits/stdc++.h>
using namespace std;
typedef struct AVLNode *AVLTree;
struct AVLNode{
	int value;
	AVLTree left,right;
	int height;
}; 
int Max(int a,int b);
AVLTree LL_Rotation(AVLTree T);
AVLTree LR_Rotation(AVLTree T);
AVLTree RR_Rotation(AVLTree T);
AVLTree RL_Rotation(AVLTree T);
AVLTree CreateTree(int n);
AVLTree Insert(AVLTree T,int a);
int GetHeight(AVLTree T);//需注意,很重要 
void ReadTree(AVLTree T);
int GetHeight(AVLTree T){
	if(!T)	return -1;
	return T->height;
}
AVLTree CreateTree(int n){
	int a;
	AVLTree T = new AVLNode();
	cin>>a;
	T->value = a;
	T->left = T->right = NULL;
	T->height = 0;
	for(int i = 1; i < n; i++){
		cin>>a;
		T = Insert(T,a);
	}
	return T;
}
AVLTree Insert(AVLTree T,int a){
	if(!T){
		T = new AVLNode();
		T->value = a;
		T->left = T->right = NULL;
		T->height = 0;
	}
	else if(a > T->value){
		T->right = Insert(T->right,a);
		if(GetHeight(T->left) - GetHeight(T->right) == -2){//右子树更重,因此是R_旋转 
			if(a > T->right->value)	T = RR_Rotation(T);//a比右子树更大,即a所放置的地方在右边,因此执行RR旋转 
			else	T = RL_Rotation(T);//反之,a所放置的地方在左子树的左边,因此执行RL旋转,下同 
		}
	}else if(a < T->value){
		T->left = Insert(T->left,a);
		if(GetHeight(T->left) - GetHeight(T->right) == 2){
			if(a < T->left->value)	T = LL_Rotation(T);
			else	T = LR_Rotation(T);
		}
	}
	T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1; 
	return T;
}
int Max(int a,int b){
	return a>b?a:b;
}
AVLTree LL_Rotation(AVLTree T){
	AVLTree AVT = T->left;//LL旋转,即让B的右子树连到A的左子树,B的左子树变成A 
	T->left = AVT->right;
	AVT->right = T;
	T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
	AVT->height = Max(GetHeight(AVT->left), T->height) + 1;
	return AVT;
}
AVLTree LR_Rotation(AVLTree T){
	T->left = RR_Rotation(T->left);//如ABC三个进行LR旋转,结果是CBA(先序遍历顺序,下同),可先对BC进行RR旋转,也就是BC换位 
	return LL_Rotation(T);//BC换位成功后顺序是ACB,再对AC进行LL旋转,也就是AC换位,这样就出来CBA了 
}
AVLTree RR_Rotation(AVLTree T){
	AVLTree AVT = T->right;
	T->right = AVT->left;
	AVT->left = T;
	T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
	AVT->height = Max(GetHeight(AVT->left), T->height) + 1;
	return AVT;
}
AVLTree RL_Rotation(AVLTree T){
	T->right = LL_Rotation(T->right);
	return RR_Rotation(T);
}
void ReadTree(AVLTree T){
	if(T){
		cout<<T->value<<' ';
		ReadTree(T->left);
		ReadTree(T->right);
	}
	else return;
}
int main(){
	int n;
	cin>>n;
	AVLTree T = CreateTree(n);
	ReadTree(T); 
//	cout<<T->value<<endl;
	return 0;
}
联系我们 沪ICP备2021010478号-7