AVL树是一种平衡二叉搜索树，其特点是左侧子树与右侧子树的高度差的绝对值是0和1。
AVL树实例图
AVL树旋转、插入、删除操作
1、AVL树旋转子树
即交换子树节点的位置，旋转后的AVL树依旧遵循高度平衡规则。左旋转，右侧节点的排列被转换为左侧节点的排列。前后如下图：
右旋转，左侧节点的排列被转换为右侧节点的排列。前后如下图：
平衡旋转，有2种情况，一是先左旋转后右旋转，排列首先向左移动，再向右移动；二是先右旋转再左旋转，排列首先向右移动，再向左移动。如下图：
先左旋转后右旋转。
先右旋转再左旋转。
2、插入新节点
初始二叉树。
设要插入的节点“9”，首先遍历初始二叉树左侧子树和右侧子树，再考虑AVL树高度平衡规则，则得出最后的二叉树结构，如下图：
3、删除节点
删除节点后，AVL树的平衡发生变化。为了重新平衡，需要执行适当的旋转。
首先，定位要删除的节点，根据节点是否存在子节点，进行替换删除，考虑高度平衡规则，需要旋转来平衡。
替换要删除的节点。
删除节点W，并更新。
向右旋转以平衡树。
最终得到Avl树，如下图：
