天津市网站建设_网站建设公司_服务器部署_seo优化

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)的平衡因子