AVL树

引言

在介绍二叉平衡树之前，有必要先了解下二叉树，下面是基于维基百科对二叉树的解释

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒

二叉树的第i层至多拥有2^(i-1)个节点。深度为k的二叉树至多总共有2^(k+1) - 1个节点（定义根节点所在深度k0 = 0），而总计拥有节点数匹配的，称为满二叉树

深度为k有n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(log n)。但是，一旦这棵二叉查找树演化成了线型树的时候，此时查询的时间复杂度会降至O(n)。

虽然二叉查找树的最坏效率是O(n)，但是他有很多改进版的二叉查找树可以使树高为O(log n)，从而将最坏效率降至O(log n)。如AVL树、红黑树这两种都是平衡二叉树，本期我们写的就是AVL树。

什么是AVL树

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1（这个高度差就是下文要提到的平衡因子），因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

平衡因子

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来

AVL 旋转

进行旋转的原因

因为AVL树需要维持节点的平衡因子为1，0，-1，固当插入新节点导致平衡因子不满足时需要进行调整以重新维持AVL树的平衡状态，这个调整过程就是旋转

旋转分类

实现简单描述

在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下：

1. 若BBST为空树，则插入一个数据元素为e的新节点作为BBST的根节点，树的深度增1；
2. 若e的关键字和BBST的根节点的关键字相等，则不进行；
3. 若e的关键字小于BBST的根节点的关键字，而且在BBST的左子树中不存在和e有相同关键字的节点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：
   1. BBST的根节点的平衡因子为-1（右子树的深度大于左子树的深度，则将根节点的平衡因子更改为0，BBST的深度不变；
   2. BBST的根节点的平衡因子为0（左、右子树的深度相等）：则将根节点的平衡因子更改为1，BBST的深度增1；
   3. BBST的根节点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根节点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；
4. 若e的关键字大于BBST的根节点的关键字，而且在BBST的右子树中不存在和e有相同关键字的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

尾言

本文介绍了AVL自平衡二叉树，所有操作的最坏复杂度都是的O(log n)。