一、AVL树（平衡二叉树）的由来
查找、插入、删除平均 / 最坏时间复杂度均为 O(logn)
AVL（平衡二叉树）树首先是一个BST（二叉搜索树）树
因为BST树进行大量的插入和删除操作可能会导致BST树退化，所以我们为了避免其退化，从而在BST树插入和删除操作执行之后多加一个平衡操作（相当于一旦发现其有劣化的趋势，则立刻通过旋转操作将其优化一下）
![]()
二、AVL的定义
避免BST树的劣化
AVL树对于平衡的定义：AVL认为所有的节点的左右子树的高度差不能超过1
（平衡因子：左子树高度-右子树高度）
通过旋转操作将失衡变成平衡：
单旋：单左旋，
LL型（单左旋）：
RR型（单右旋）：
LR型：第一次旋转是对失衡节点的孩子 第二次旋转对失衡节点自身
RL型：
失衡
三、AVL树的删除
非递归逻辑：
1.先调用查找函数，去查找待删除节点，是否存在
2.如果不存在，则直接结束，无需调整
3.如果存在该节点，则按照BST逻辑，先去判断该待删除节点是什么类型：
3.1 判断该节点是双分支 =>狸猫换太子
3.2 如果该节点是单分支 =>直接让其父节点指向其孩子节点
3.3 如果该节点是零分支 =>直接让其父节点抓向其节点的手置为NULL即可
AVL删除非递归逻辑：
1.判断当前root是否存在
2.如果当前root等于NULL，则说明待删除节点不存在（或者当他存在，只不过被我们释放掉了），直接返回NULL让上一层来接受
3.如果当前root不等于NULL，则说明存在，则将其root->data和待删除val比较
4.此时待删除val值节点删除完之后，返回值被上一层root接收之后，只需要对接收的root做两件事即可：
4.1更新root高度
4.2调用Rotate通用旋转函数去给root做检查
