AVL树学习总结

AVL树是一种特殊的二叉搜索树，由两位俄国数学家G.M.Adelson-Velskii和E.M.Landis所发明，所以取名AVL树。AVL树本质上是一种平衡的二叉搜索树

一、基本概念

1、AVL树需要满足：

• 每一个节点的左子树和右子树高度差至多为1
• 满足二叉搜索树的性质

2、平衡因子（Balance Factor, BF）：左子树高度 - 右子树高度，因此，由AVL的条件可知，一颗AVL树，它的BF的取值范围只能是{-1, 0, 1}
3、最小不平衡子树：离插入节点最近，且|BF| > 1的节点为根的子树

二、实现原理

AVL树需要在每次树的结构发生改变的时候，计算BF，通过旋转调整来使得BF取值为{-1, 0, 1}内，且同时符合二叉搜索树的性质。旋转总共有4种情况，如下：
1、BF > 1，最小不平衡子树根节点的BF和其左子树根节点的BF符号相同，则 右旋：

步骤：

• 保存左子树的根节点为L
• 由二叉搜索树的性质，可知P左边的所有节点数值都小于它的数值。所以，旋转后，P->left = L->right
• L->right = P
• 根节点替换为L

实现：

void rotateR(AVLNode* p) {
    AVLNode* L;
    L = p->left;
    p->left = L->right;
    L->right = p;
    p = L;
}

2、BF < -1，最小不平衡子树根节点的BF和其右子树根节点的BF符号相同，则 左旋：

步骤：

• 保存右子树的根节点为R
• 因为R的左子树的节点值肯定大于P，所以应该成为P的右子树。P->right = R->left
• R->left = P
• 根节点替换为R

实现：

void rotateL(AVLNode* p) {
    AVLNode* R = p->right;
    p->right = R->left;
    R->left = p;
    p = R;
}

3、最小不平衡子树的根节点的BF和其子树根节点的BF符号不同，且子树根节点BF < -1时，先左旋子树，使得BF值符号相同后，再进行一次旋转，如：

4、同理，最小不平衡子树的根节点的BF和其子树根节点的BF符号不同，且子树根节点BF > 1时，先右旋子树，使得BF值符号相同后，再进行一次旋转

三、性能

AVL相比普通的二叉搜索树，最大的优点是不会出现退化为链表，导致查找时间为O(n)的情况。因为AVL树的每次结构变化，都会进行平衡操作，如此一来，能够使得AVL树的查找操作的时间复杂度为O(logn)，插入删除也为O(logn)