平衡二叉搜索树(AVL树)

定义：

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

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

特性

旋转

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

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

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