关于树的一些基础理论请参照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插入-右左单旋
这样，将被破坏平衡的二叉搜索树，在保持其二叉搜索树的特性的前提下重新使其平衡。
网友评论