AVL树简介

一、AVL树简介

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

一棵AVL树有如下必要条件：

1. 它必须是二叉查找树。
2. 每个节点的左子树和右子树的高度差至多为1。

二、AVL树相关概念

平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。

对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。

如图所示，左图中88的左右子树高度之差为2，即88这个节点的平衡因子为2，需要进行调整，调整后如右图，70的左右子树高度之差为0，即70这个节点的平衡因子为0.

三、AVL树的平衡调整

1. LL型调整：

由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下图是LL型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。（这里我们称为右旋）

LL型调整的一般形式如下图所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。
这种情况调整如下：

1. 将A的左孩子B提升为新的根结点；
2. 将原来的根结点A降为B的右孩子；
3. 各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。

代码实现

void R(node* &root){
   
    node *temp = root->left;
    root->left = temp->right;
    temp->right = root;
    root = temp;
}
1
2
3
4
5
6
7

2. RR型调整：

由于在A的右孩子®的右子树®上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。下图是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。(这里我们称为左旋）

RR型调整的一般形式如下图所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。
这种情况调整如下：

1. 将A的右孩子B提升为新的根结点；
2. 将原来的根结点A降为B的左孩子
3. 各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。

代码实现

void L(node* &root){
   
    node *temp = root->right;
    root->right = temp->left;
1
2
3