数据结构之平衡二叉树（AVL）

╰+攻爆jí腚メ 2023-03-01 11:54 24阅读 0赞

平衡二叉树是指\*\*左右子树高度不超过1（平衡因子）\*\*的有序二叉树  
设一个高度为h的平衡二叉树，其最少结点数为：`Nh = Nh-1+Nh-2+1`,有点类似斐波那契数列

平衡二叉树的调整：  
**（1）RR旋转**  
新插入的结点在右子树的右子树上，因此叫做RR插入；  
比如有ABC三个结点，A是跟结点，B是右孩子，C是刚插入的结点，因为C的插入，二叉树的高度发生了变化。  
调整的时候，新插入的结点C的高度上升，B从孩子变为了跟结点，原来的跟结点A变成了B的左孩子，C变成了B的右孩子，这样的方式叫做RR旋转。  
![浙大数据结构][2020072421523892.png]  
用上面这个图再次进行解释：  
右下角蓝色区域是新插入的结点，原来树的高度差是1，插入之后变成了2，插入的位置是A的右孩子的右子树，调整的时候，新插入的结点跟Br地位上升，变为B的右子树，而原来Bl则要挂到A的右子树去，因为Bl比A的值大，还需要保持搜索树的特性。

**（2）LL旋转**  
新插入的结点在左子树的左子树上，因此叫做LL插入；  
![来自浙大数据结构][20200724215856134.png]  
左下角是新插入的结点，原来树的高度差是1，插入之后高度差发生了变化，受到影响的是结点A，引起变化的是插入的蓝色部分，其插入在A的左子树的左子树上，因此被称为LL插入。调整时，A的左子树B的地位上升，成为父节点，B的右子树则放到A的左子树去，保持搜索树的性质。  
**（3）LR旋转**  
新插入的结点在左子树的右子树上，叫做LR插入  
![浙大数据结构][20200724230026969.png]  
蓝色区域是新插入的内容，其位于根节点A的左子树B的右子树C上，因此称作LR插入。受到影响的结点时A，引起变化的结点在A的左子树B的右子树C上。调整时，重点关注ABC三者之间的大小，将原来的右子树C作为根节点，原来C的左子树作为B的右子树，原来C的右子树作为A的左子树，保持了搜索树的性质。  
**（4）RL旋转**  
新插入的结点在右子树的左子树上，叫做RL插入  
![浙大数据结构][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70]  
蓝色区域是新插入的内容，其位于根节点的右子树的左子树上，因此称作RL插入。此时收到影响的结点时A，引起高度差变化的结点在A的右子树B的左子树C上。调整时，重点关注ABC三者之间的大小，将原来的B的左子树C作为根节点，比C小的结点挂在左边，比C大的结点挂在右边，保持了搜索树的性质。

**假设平衡因子是由左子树的高度减去右子树的高度**，总结起来，就是如下的样子：  
**若左子树的当前高度为2，说明为LL型，要向右调整，调整时，判断当前结点的高度为，如果是1，则是左子树，直接调，如果是-1，说明右子树，先向左，再向右；若当前高度为-2，说明是RR型，整体向左调整，若当前结点为1，是右子树，直接调，-1，先往右再往左；**

给出一个完整的AVL树的创建、调整和获取根节点的代码，很痛苦，还不怎么用…

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct node{
        						//定义结点的值跟高度 
    	int data, height;
    	node *left, *right;
    }*root;
    node *newNode(int data)				//申请一个新的结点 
    {
        
    	node *Node = new node;
    	Node->data = data;
    	Node->left = Node->right = NULL;
    	Node->height = 1;				//新申请的结点的高度是1 
    	return Node;
    }
    int getHeight(node *root)			//获取根节点的高度 
    {
        
    	if(root == NULL)	return 0;
    	return root->height;
    }
    int upHeight(node *root)			//更新根节点的高度 
    {
        
    	root->height = max(getHeight(root->left), getHeight(root->right))+1;
    }
    int getBlance(node *root)			//获取左右子树之间的高度差 
    {
        
    	return getHeight(root->left) - getHeight(root->right);
    }
    void LL(node *&root)				//LL旋转，即向右调整 
    {
        
    	node *temp = root->right;		//将根节点的右子树暂存 
    	root->right = temp->left;		//将暂存节点的左子树，作为根节点的右子树 
    	temp->left = root;				//将暂存节点的左子树变为根 
    	upHeight(root);					//更新根节点的高度 
    	upHeight(temp);					//更新新的根节点的高度 
    	root = temp;					//将暂存节点变为根节点 
    }
    void RR(node *&root)				//RR旋转，即向左调整 
    {
        
    	node *temp = root->left;		//将根节点的左子树暂存 
    	root->left = temp->right;		//将暂存节点的右子树作为根节点的左子树 
    	temp->right = root;				//将暂存节点的右子树变为根 
    	upHeight(root);					//更新根节点的高度 
    	upHeight(temp);					//更新暂存节点的高度 
    	root = temp;					//暂存节点变为根节点 
    } 
    void insert(node *&root, int data)	//创造AVL树 
    {
        
    	if(root == NULL)				//新建根节点 
    	{
        
    		root = newNode(data);
    		return;
    	}
    	if(data <root->data)			//往左子树上插入数据 
    	{
        
    		insert(root->left, data);
    		upHeight(root);				//更新根节点高度 
    		if(getBlance(root) == 2)	//左子树比右子树高
    		{
        
    			if(getBlance(root->left) == 1)
    				RR(root);			//插入节点在左子树的左子树上，向右调整 
    			else if(getBlance(root->right) == -1)//
    			{
        						//插入节点在左子树的右子树上，先左后右 
    				LL(root->left);
    				RR(root);
    			}
    		}
    	}else							//往右子树插入数据 
    	{
        
    		insert(root->right, data);
    		upHeight(root);				//更新节点高度 
    		if(getBlance(root) == -2)	//右子树高 
    		{
        
    			if(getBlance(root->right) == -1)
    				LL(root);			//在右子树的右子树上，向左调整 
    			else if(getBlance(root->left) == 1)
    			{
        						//在右子树的左子树上，先右后左 
    				RR(root->right);
    				LL(root);
    			}
    		}		
    	} 
    }
    node *create(int data[], int n)
    {
        
    	node *root = NULL;
    	for(int i=0; i<n; i++)
    	{
        
    		insert(root, data[i]);
    	}
    	return root;
    } 
    int main()
    {
        
    	int n, data;
    	scanf("%d",&n);
    	for(int i=0; i>n; i++)
    	{
        
    		scanf("%d",&data);
    		insert(root, data);
    	}
    	printf("%d\n", root->data);		//输出根节点位置 
    	return 0;
    }

参考资料：  
[https://www.bilibili.com/video/BV1JW411i731?p=44][https_www.bilibili.com_video_BV1JW411i731_p_44]

[2020072421523892.png]: /images/20230208/e1f7ac2937b04eeeb0da3dcb4b7a38f9.png
[20200724215856134.png]: /images/20230208/e35baa811cf942218a4dc45ab5577967.png
[20200724230026969.png]: /images/20230208/5ce61bf1f57f4a9992d78d714e1d3828.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70]: /images/20230208/249b84d0627a4948a02d422b1a209fe9.png
[https_www.bilibili.com_video_BV1JW411i731_p_44]: https://www.bilibili.com/video/BV1JW411i731?p=44