AVL树
- AVL树是最早发明的自平衡二叉搜索树之一
- 平衡因子（Balance Factor）：某节点左右子树的高度差
- AVL树特点
- 每个节点的平衡因子只可能是 -1、0、1（绝对值<=1，如果大于1，就是失衡）
- 每个节点左右子树的高度差不超过1
- 搜索、添加、删除的时间复杂度是O(log n)
平衡对比
添加导致的失衡
LL-右旋转（单旋）
RR-左旋转（单旋）
LR-先左旋parent变成LL，再右旋grand（双旋）
RL-先右旋parent变成RR，再左旋grand（双旋）
删除导致的平衡
若有收获，就点个赞吧
0 人点赞
