关于树的一些基础理论请参照https://blog.51cto.com/4259297/1708154
由于AVL树涉及到树的旋转概念，所以单独成文。
https://blog.csdn.net/weixin_30363263/article/details/85702725

概念

AVL树是平衡二叉树和二叉搜索树的合体，也叫做”平衡二叉搜索树“。
特征：

AVL树是一棵二叉搜索树。
AVL树的左右子节点也是AVL树。
AVL树拥有二叉搜索树的所有基本特点。

每个节点的左右子节点（同一层的兄弟结点）的高度之差的绝对值最多为1，即平衡因子为范围为[-1,1]。

两个重要的操作

插入

所谓的插入，是指在平衡二叉树的基础上插入新的节点。分为4种：

• LL插入
• RR插入
• LR插入
• RL插入

旋转

https://blog.csdn.net/qq_24336773/article/details/81712866

由于在平衡二叉树的基础上插入新的节点会导致树的不平衡，所以必须对不平衡的节点（插入的新节点父结点的父结点）进行旋转，针对上面的插入类型，对应的旋转类型为：

• LL插入-左单旋
• RR插入-右单旋
• LR插入-左右单旋
• RL插入-右左单旋
  这样，将被破坏平衡的二叉搜索树，在保持其二叉搜索树的特性的前提下重新使其平衡。