AVL树——一种平衡的BST
普通BST的问题：不平衡
树的平衡性是很重要的，在BST中，查找的时间复杂度为O(h)，其中h为树高，如果树不平衡，树可能会退化为一个链表，此时时间复杂度会变为O(n)。普通的BST不具有平衡的特性，所以我们需要对其进行改进。平衡的二叉树高度为lg(n)，而不平衡的二叉树，高度最坏情况下为O(n)。其中，树的高度的定义为：从根节点到叶子节点的最长路径的长度。
- 平衡：h=lgn
- 不平衡：h=n
AVL树
我们先定义节点的高度，一个节点的高度为从该节点到一个叶子节点的最长路径，即：
hn=max(path)=max{height(left),height(right)}+1我们规定叶子节点的高度为0，空节点的高度为-1。而AVL树的目标就是使节点高度尽可能小。
定义
AVL树的性质：每一个节点的左右子节点的高度差最大为1，即：
|hr−hl|≤1根据这个性质，AVL树是一种平衡树，最坏情况下，每一个右子树都比左子树高1。
令$Nh为一棵高度为h的AVL树的最小节点数，现在我们来证明最坏情况下N_h和h之间的关系。根据AVL树高的定义，我们规定N{O(1)}=O(1)，而N_h$为：
Nh=1+Nh−1+Nh−2其中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排序
只需要进行中序遍历即可，时间复杂度为Θ(n)，而插入n个元素所需的时间复杂度为Θ(nlgn)