AVL 树：旋转、插入、删除 C++ 例如：
陈莎拉
什么是 AVL 树？
AVL 树 是二叉搜索树，其中左子树和右子树的高度差为 -1、0 或 +1。
AVL 树也称为自平衡二叉搜索树。这些树有助于保持对数搜索时间。它以其发明者 (AVL) Adelson、Velsky 和 Landis 的名字命名。
AVL 树如何工作？
为了更好地理解 AVL 树的必要性，让我们看看简单二叉搜索树的一些缺点。
考虑按给定顺序插入二叉搜索树中的以下键。
当我们按键值的升序插入键时，树的高度会线性增长。因此，搜索操作最坏情况下需要 O(n)。
搜索元素需要线性时间；因此没有必要使用 二进制搜索树 结构。另一方面，如果树的高度平衡，我们可以获得更好的搜索时间。
现在让我们看一下以不同顺序插入的相同键。
这里，键是相同的，但由于插入顺序不同，它们占据不同的位置，树的高度保持平衡。因此，对于树中的任何元素，搜索时间都不会超过 O(log n)。现在很明显，如果插入正确，树的高度可以保持平衡。
在 AVL 树中，我们在插入操作期间检查树的高度。进行修改以保持平衡高度，而不会违反二叉搜索树的基本属性。
AVL 树中的平衡因子
平衡因子 (BF) 是 AVL 树中每个节点的基本属性，有助于监控树的高度。
平衡因子的性质
- 平衡因子称为左子树和右子树的高度之差。
- 平衡因子（节点）= 高度（节点->左）- 高度（节点->右）
- BF 的允许值为 –1、0 和 +1。
- 值 -1 表示右子树包含一个额外元素，即该树是右重树。
- 值 +1 表示左子树包含一个额外元素，即该树为左重子树。
- 值 0 表示树的每一侧包含相等的节点，即树是完全平衡的。
AVL 旋转
为了使 AVL 树自身平衡，在树中插入或删除节点时，需要进行旋转。
我们执行以下 LL 旋转、RR 旋转、LR 旋转和 RL 旋转。
- 左 – 左旋转
- 右 – 右旋转
- 右 - 左旋转
- 左 - 右旋转
左 – 左旋转
当在左子树的左孩子处插入新节点时，执行此旋转。
执行一次右旋转。当节点的平衡因子为 +2，且其左子节点的平衡因子为 +1 时，可识别出这种类型的旋转。
右 – 右旋转
当在右子树的右孩子处插入新节点时，执行此旋转。
执行一次左旋转。当节点的平衡因子为 -2，且其右子节点的平衡因子为 -1 时，可识别出这种类型的旋转。
右 - 左旋转
当在左子树的右孩子处插入新节点时，执行此旋转。
当某个节点的平衡因子为 -2，而其右子节点的平衡因子为 +1 时，就会执行此旋转。
左 - 右旋转
当在右子树的左孩子处插入新节点时，执行此旋转。
当某个节点的平衡因子为 +2，而其左子节点的平衡因子为 -1 时，就会执行此旋转。
AVL 树中的插入
插入操作与简单的二叉搜索树几乎相同。每次插入后，我们都会平衡树的高度。插入操作的最坏时间复杂度为 O(log n)。
第一步：使用与 BST 相同的插入算法将节点插入 AVL 树中。在上面的示例中，插入 160。
第一步：每次添加节点，更新每个节点的平衡因子。插入160后，更新每个节点的平衡因子。
第一步：现在检查是否有任何节点违反了平衡因子的范围，如果违反了平衡因子，则使用以下情况执行旋转。在上面的例子中，平衡因子 350 被违反，并且情况 1 在那里适用，我们执行 LL 旋转并且树再次平衡。
- 如果 BF(node) = +2 且 BF(node -> left-child) = +1，则执行 LL 旋转。
- 如果 BF(node) = -2 且 BF(node -> right-child) = 1，则执行 RR 旋转。
- 如果 BF(node) = -2 且 BF(node -> right-child) = +1，则执行 RL 旋转。
- 如果 BF(node) = +2 且 BF(node -> left-child) = -1，则执行 LR 旋转。
AVL 树中的删除
删除也非常简单。我们使用与简单二叉搜索树相同的逻辑进行删除。删除后，我们会根据需要重组树以保持其平衡高度。
步骤1： 在树中查找元素。
步骤2： 按照 BST 删除方法删除节点。
步骤3： 有两种情况可能：-
案例1： 从右子树删除。
- 1A. 如果 BF(node) = +2 且 BF(node -> left-child) = +1，则执行 LL 旋转。
- 1B. 如果 BF(node) = +2 且 BF(node -> left-child) = -1，则执行 LR 旋转。
- 1C. 如果 BF(node) = +2 且 BF(node -> left-child) = 0，则执行 LL 旋转。
案例2：从左子树删除。
- 2A. 如果 BF(node) = -2 且 BF(node -> right-child) = -1，则执行 RR 旋转。
- 2B. 如果 BF(node) = -2 且 BF(node -> right-child) = +1，则执行 RL 旋转。
- 2C. 如果 BF(node) = -2 且 BF(node -> right-child) = 0，则执行 RR 旋转。
C++ AVL 树的示例
下面是 C++ 实现 AVL 树：
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
上述代码的运行示例：
- 复制上面的代码并粘贴到“avl.cpp”。
- 编译代码：
g++ avl.cpp -o run
- 运行代码。
./run
AVL 树的优点
- AVL 树的高度始终是平衡的。高度永远不会超过 log N，其中 N 是树中的节点总数。
- 与简单的二叉搜索树相比，它具有更好的搜索时间复杂度。
- AVL 树具有自平衡能力。
结语
- AVL 树是自平衡二叉搜索树。
- 平衡因子是 AVL 树的基本属性
- 节点的平衡因子定义为该节点左子树和右子树的高度之差。
- 平衡因子的有效值为 -1、0 和 +1。
- 插入和删除操作需要在违反平衡因素后进行旋转。
- 插入、删除和查找操作的时间复杂度为O(log N)。
- AVL 树遵循二叉搜索树的所有属性。
- 左子树的节点小于根节点，右子树的节点始终大于根节点。
- 与插入和删除操作相比，搜索操作更频繁的地方使用 AVL 树。
