AVL树——一种平衡的BST
普通BST的问题：不平衡
树的平衡性是很重要的，在BST中，查找的时间复杂度为$O(h)$，其中$h$为树高，如果树不平衡，树可能会退化为一个链表，此时时间复杂度会变为$O(n)$。普通的BST不具有平衡的特性，所以我们需要对其进行改进。平衡的二叉树高度为$\lg (n)$，而不平衡的二叉树，高度最坏情况下为$O(n)$。其中，树的高度的定义为：从根节点到叶子节点的最长路径的长度。
- 平衡：$h=\lg n$
- 不平衡：$h=n$
AVL树
我们先定义节点的高度，一个节点的高度为从该节点到一个叶子节点的最长路径，即：
我们规定叶子节点的高度为0，空节点的高度为-1。而AVL树的目标就是使节点高度尽可能小。
定义
AVL树的性质：每一个节点的左右子节点的高度差最大为1，即：
根据这个性质，AVL树是一种平衡树，最坏情况下，每一个右子树都比左子树高1。
令$Nh$为一棵高度为$h$的AVL树的最小节点数，现在我们来证明最坏情况下$N_h$和$h$之间的关系。根据AVL树高的定义，我们规定$N{O(1)}=O(1)$，而$N_h$为：
其中1为根节点，$N{h-1}$为右子树节点，$N{h-2}$为左子树节点。由这个公式可以推导出，$h<1.44\lg n$。所以高度被限制在了$O(\lg n)$。
操作
插入
- 做一个基本的BST操作
- 调整树，使得其符合AVL的性质
现在我们以一个简单的插入操作为例，看一下AVL树的插入过程：
情况1：右子树中插入右节点（或左子树中插入左节点）
假设我们有一棵AVL树，现在要插入一个新节点23，根据插入操作的顺序，我们先将节点23按照BST的定义插入，然后再对树进行调整。
插入节点后，树不平衡了，我们需要平衡化，就是绕着某个节点进行旋转，其过程示意图如下：
这个操作叫做绕着$x$的左旋转（如果固定$x$，$y$是逆时针在转动），left_rotate(x)，这个操作的时间复杂度为$O(1)$，同时，这个操作也保持了树的BST特性。根据对称性，如果在左子树插入左节点，那么是做一个右旋转。
情况2：左子树中插入右节点（或右子树中插入左节点）
而另一种情况更加复杂，如果在左子节点插入右子树，或者在右子节点插入左子树，我们就不能通过一次旋转解决，而是需要两次。此时旋转过程如下：
现在我们来总结一下插入的过程：
假设$x$是最低的违背AVL性质的节点
假设right$(x)$是更高的子树
- 如果$x$的右子节点的右子树是平衡的或者right-heavy的，那么就右旋转$x$
- 如果$x$的右子节点的左子树是left-heavy的，那么先RR(z)，在LR(x)
应用
AVL排序
只需要进行中序遍历即可，时间复杂度为$\Theta(n)$，而插入$n$个元素所需的时间复杂度为$\Theta(n\lg n)$