平衡二叉树

定义

平衡二叉树，又称AVL树，它是一种特殊的二叉排序树。AVL树或者是一棵空树，或者是具有以下性质的二叉树：

1. 左子树和右子树都是平衡二叉树；
2. 左子树和右子树的深度（高度）之差的绝对值不超过1。

操作

AVL树的操作与BST树很相似，区别比较大的操作是插入和删除，由于AVL树要求左右子树的高度差不能超过1，所以当插入和删除结点之后，都需要进行树的平衡操作，以保证仍然是一颗AVL树。

旋转

在介绍插入和删除之前，先来了解下保证树平衡的关键操作——旋转，针对不同的情况，有不同的旋转方式，如：

• LL 左左旋转，用于处理导致最下层失衡结点失衡的是左子树的左子树的情况
• LR 左右旋转，用于处理导致最下层失衡结点失衡的是左子树的右子树的情况
• RL 右左旋转，用于处理导致最下层失衡结点失衡的是右子树的左子树的情况
• RR 右右旋转，用于处理导致最下层失衡结点失衡的是右子树的右子树的情况

LL 和 RR 的操作是对称的，LR 和 RL的操作也是对称的，所以我们仅需要记住 LL 和 LR 旋转就可以了。

LL 旋转

将失衡结点的左孩子的右孩子赋给失衡结点的左孩子，原左孩子的替代失衡结点，失衡结点作为原左孩子的右孩子。

伪代码
function llRotate(root){
    node = root->left;
    root->left = node->right;
    node->right = root;
    
    return node;
}

LR 旋转

对失衡结点的左孩子做 RR 旋转，然后对失衡结点做 LL 旋转。

伪代码
function lrRotate(root){
    root->left = rrRotate(root->left);
    return llRotate(root);
}

插入和删除

插入和删除结点后，判断二叉树是否仍是平衡二叉树，如果是则完成插入或删除，如果不是，则找到失衡结点，判断是那种情况，然后采用不同对旋转方式使树恢复平衡即可。

总结分析

• AVL树相对于BST树来说，高度更小了，查询时的次数更少了，但是维护树的成本更高了。
• AVL树在数据量小的时候能够保证树的高度小，当数据量大的时候，仍然会是一颗很高的树，查询的性能也会随之下降，要解决这种情况的问题，可以改变结点的孩子数，使二叉树变为多叉树，以此降低树的高度，减少比较次数，提高查询效率。