AVL(Adelson-Velsky and Landis Tree) 树是一种自平衡二叉树, 也是最早发明的一种自动平衡二叉树 。原因是由于BST(二叉搜索树)在用有序列表不断插入时会退化成链表而大大影响其效率，因此最早计算机科学家G. M. Adelson-Velsky和Evgenii Landis在1962年发明了AVL树 。首先要明确AVL树是一种二叉搜索树(BST)，不了解BST的同学可以看我之前的一篇文章<<数据结构---二叉搜索树>> 。AVL树中的任意节点的两颗子树高度差<=1 。因此AVL树是高度平衡的 。如下图所示的就是一颗AVL树 。每个节点都标注了其高度 。
文章插图
在AVL树中把每个节点的左子树高度减去其右子树高度差定义为平衡因子 。在AVL树中只有平衡因子大于等于-1并且小于等于1才是平衡的 。因此平衡因子只能取3个值-1, 0和1 。平衡因子取其它值被认为是不平衡的，就需要对该AVL树进行调整，以使其达到平衡 。
当一颗AVL树不平衡时，我们需要对其进行一系列操作使其保持平衡，下面介绍AVL树的基本操作 。
- 左旋
文章插图
上图是节点的原始状态，绕y节点进行左旋的步骤如下：
- 如果β不为空将β的parent设为x，同时将x的右孩子设为β 。
文章插图
- 如果p是NULL，将y设为根节点 。
- 否则如果x是p的左孩子，将y设为p的左孩子
- 否则将y设为p的右孩子
- 将p设为y的父节点
文章插图
- 将y设为x的父节点，将x设为y的左孩子，完成左旋 。
文章插图
- 右旋
文章插图
上图是节点的原始状态，绕x节点进行右旋的步骤如下：
- 如果β不为空，将β的父节点设为y，同时将y的左孩子设为β 。
文章插图
- 如果p是NULL，将x设为根节点
- 否则，如果y是p的右孩子，将p的右孩子设为x
- 否则，将p的左孩子设为x
- 将x的父节点设为p
文章插图
- 将x设为y的父节点，将y设为x的右孩子，完成右旋
文章插图
- 左右旋转(LR)
文章插图
然后再以y为中心对z进行右旋，完成平衡调整 。
文章插图
- 右左旋转(RL)
文章插图
然后再以y为中心对z进行左旋，完成平衡调整 。
文章插图
上面我们介绍了AVL树的基本操作，下面我们介绍AVL树的插入和删除算法 。
- 插入算法
文章插图
上图所示的AVL数每个节点的值和平衡因子都标了出来 。它现在处于平衡状态，因为它的每个节点的平衡因子(左子树高度减去右子树高度的值)都满足要求(大于等于-1并且小于等于1) 。现在假设我插入一个值为9的节点，我们来分步看看插入算法的整个过程 。
- 首先按照BST的插入算法，插入值为9的节点 。插入后，如下图所示:
文章插图
- 可以看到，上面的树不再平衡，因为树中有三个节点的平衡因子为2，所以需要对其进行调整使其满足AVL树的性质 。调整如下：
推荐阅读
- 电脑故障大全---主板
- 华为架构师整理Redis数据结构的大厂最佳实践
- 简单分析实现运维利器---web远程ssh终端录像回放
- Redis常用的数据结构
- 装机入门之---如何挑选电源
- 摄像机监控镜头变焦与变倍分析
- 重生之纯悫皇贵妃耿默薇胤禛,纯懿皇贵妃耿氏---端妃
- 常用数据结构
- Mysql索引数据结构有多个选择，为什么一定要是B+树？
- python基础——数据结构栈的详解