在本章中，我们将学习以下主题：
- AVL树介绍
- 需要AVL树吗？
- LL旋转
- RR旋转
- 左旋
- RL旋转
-
AVL树简介：
如果满足以下两个属性，则可以将其称为AVL树：
- 它应该是二进制搜索树
- 平衡因子应为{-1，0，1}
-
该树应为BST。
在上一章中，我们了解了BST，但将简要介绍什么是BST。
如果树的左侧元素小于父级值，而右侧元素大于父级值，则称为BST。并且BST中不允许重复值。
-
平衡因素：
每个节点的平衡因子应为{-1，0，1}。可以通过以下公式计算任何节点的平衡系数：
Balancing_factor = height_of_left_sub_tree – height_of_right_sub_tree。
结果应为{-1，0，1}。差异称为平衡因子。
-
需要AVL树吗？
也许有人会想，当我们拥有BST时，为什么我们需要AVL树。
考虑元素{1,2,3}。 BST可以根据元素的位置以不同的方式构造。
例如：
- 如果元素为{1、2、3}，则BST可以如下所示：
- 如果元素为{2，3，1}，则BST为
- 如果元素为{3,1,2}，则BST为
如您所见，根据元素的位置，树结构会发生变化。但是，如果使用AVL树，树结构将保持不变，我们将在本章中进一步介绍。
好的，现在我们将讨论上一个主题，平衡因子。
在AVL树中，每当插入元素时，都需要计算树中所有节点的平衡因子。每个节点都必须执行此步骤。
如果平衡因子不在{-1，0，1}范围内，那么我们需要使其平衡。
为了使树平衡，我们有4种不同类型的旋转。
- 左左不平衡旋转
- 右右不平衡旋转
- 左右不平衡旋转
- 左右不平衡旋转
正如您可能从上述命名约定中猜到的那样，我们根据发现的不平衡类型进行轮换。我们将在下面逐一了解这些轮换：
-
左左不平衡旋转
考虑元素{3，2，1}。
我们将逐步构建AVL树。
插入3
由于节点只有1，因此平衡因子为0。
插入2
叶节点“ 2”的平衡因子将为零。值为“ 3”的节点的平衡因子为1。因为它只有高度为1的右子节点。现在，它也是一棵AVL树。
插入1。
叶节点的值为“ 1”的平衡因子为0。
值为“ 2”的平衡因子节点为1，因为它只有右子节点
值为“ 3”的平衡因子节点为2，因为它有2个正确的子节点。因此，树不平衡。
观察下图，
左左孩子发生失衡。因此，我们说LL旋转。在这种情况下，我们需要以中间节点“ 2”为根旋转右侧
旋转后
-
右右不平衡旋转
考虑元素{1,2,3}。
插入1
插入2
插入3
现在，右对右不平衡。因此，请向左旋转2。
轮换后，最终将是
-
左右不平衡旋转
考虑元素{3，1，2}。
BST将是
现在您看到不平衡，即左右不平衡。
为了使其平衡AVL，您需要旋转2次。一种是向左旋转；另一种是向左旋转。另一个时间是右旋转。
首先向左旋转，下面是树。
下一步向右旋转，下面是最后的AVL树。
-
左右不平衡旋转
考虑元素{1,2,3}。
BST将如下所示：
现在您将看到不平衡，即右左不平衡。
为了使其平衡AVL，您需要旋转2次。一种是右旋；另一种是右旋。另一个时间是“左旋转”。
先向右旋转
首先向左旋转。下面是最终的AVL树。
从上面的4个旋转中可以看到，最终的AVL树是相同的。
所有轮换的摘要。
左左不平衡旋转-> Do Right Rotation.
右右不平衡旋转-> Do Left Rotation.
左右不平衡旋转->先左旋转，然后右旋转。
左右不平衡旋转->先右旋转，然后左旋转。
C语言中AVL TREE的实现
#include "stdio.h"
#include "stdlib.h"
//AVL Tree Node
struct Node
{
int data; // Store the data
int height; //Store the current height of node
struct Node* left; // Link to left child
struct Node* right; // Link to right node
};
//Create a new node
struct Node* NewNode(int data)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
temp->height = 1;
return temp;
}
int get_max_height(int a,int b)
{
return (a>b)?a:b;
}
int get_height(struct Node* node)
{
if(node==NULL)
return 0;
return node->height;
}
int Balance(struct Node* node)
{
if(node==NULL)
return 0;
return get_height(node->left) - get_height(node->right);
}
struct Node* LeftRotate(struct Node* a)
{
struct Node* b = a->right;
struct Node* temp = b->left;
b->left = a;
a->right = temp;
a->height = get_max_height(get_height(a->left),get_height(a->right))+1;
b->height = get_max_height(get_height(b->left),get_height(b->right))+1;
return b;
}
struct Node* RightRotate(struct Node* a)
{
struct Node* b = a->left;
struct Node* temp = b->right;
b->right = a;
a->left = temp;
a->height = get_max_height(get_height(a->left),get_height(a->right))+1;
b->height = get_max_height(get_height(b->left),get_height(b->right))+1;
return b;
}
void preorder(struct Node* root)
{
if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
struct Node* insert(struct Node* root,int data)
{
if(root==NULL)
return NewNode(data);
if(data < root->data)
root->left = insert(root->left,data);
else if(data > root->data)
root->right = insert(root->right,data);
else
return root;
root->height = get_max_height(get_height(root->left),get_height(root->right))+1;
int balance = Balance(root);
// LL imbalance case
if(balance > 1 && data < root->left->data)
return RightRotate(root);
// RR imbalance case
if(balance < -1 && data > root->right->data)
return LeftRotate(root);
// LR imbalance case
if(balance > 1 && data > root->left->data)
{
root->left = LeftRotate(root->left);
return RightRotate(root);
}
// RL imbalance case
if(balance < -1 && data < root->right->data)
{
root->right = RightRotate(root->right);
return LeftRotate(root);
}
return root;
}
int main()
{
struct Node* root = NULL;
root = insert(root,5);
root = insert(root,10);
root = insert(root,15);
root = insert(root,30);
root = insert(root,14);
root = insert(root,24);
root = insert(root,3);
printf("\nPreorder traversal of tree is : \n");
preorder(root);
return 0;
}
输出：
Preorder traversal of tree is : 15 10 5 3 14 30 24
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
