AVL树
一.概念:
1.二叉搜索树
2.所有子树高度差至多为1
3.左右子树都是AVL树
4.空树也是AVL树
二.特点
1.有(或没有)平衡因子,平衡因子 = 右子树高度 - 左子树高度 = 1/ 0/ -1
2.两个logN:高度和时间复杂度
3.高度平衡
三.结构
1.结点(AVLTreeNode):父母,左子树,右子树,平衡因子,值
2.AVL树(AVLTree):结点
四.插入
1.比较插入值kv的first从根节点的first向下开始比较,走到指定的叶子结点的子节点
2.插入后某些结点的平衡因子可能会发生改变,要进行更新:插入到左子树,平衡因子-1;插入到右子树,平衡因子+1;依次往上更新
3.更新后的平衡因子必有以下几种情况:(正常情况下,插入结点一定有平衡因子发生改变)
a 平衡因子变成+-1:继续往上判断
b 平衡因子变成0:正常结束完美结局
c 平衡因子变成+-2:坏结局,开始旋转
4.若发生旋转,再次更新平衡因子
五.旋转
a 右单旋(左边彻底高)旋转条件: 平衡因子 -2 -1
5的右给10的左,5成为10的父母
b 左单旋(右边彻底高)旋转条件: 平衡因子 2 1
15的左给10的右,15做10的父母
注意:10结点有两种情况:为根节点和非根节点
b树可能为空
定义两个结点parent 10 subL5
先改变各结点的指向,再更新平衡因子
c 左右双旋(先左高,再右高)旋转条件: 2 -1 -1
先左旋5再右旋10
最终结果:8的左给5的右,8的右给10的左,5和10做8的左右
d右左双旋(先右高再左高)
12的左给10的右,12的右给15的左,10和15为12的左右
用到三个结点parent,subL,subLR
先执行subR的左单旋,再执行parent的右单旋
最后更新平衡因子
判断条件为subRL(12)的平衡因子
