目录
1.AVL树的概念
2.AVL树的实现
2.1AVL树的结构
2.2AVL树的插入
2.2.1 AVL树插⼊⼀个值的⼤概过程
2.2.2平衡因子的更新
2.2.3 插⼊结点及更新平衡因⼦的代码实现 编辑
2.3旋转
2.3.1旋转的原则
2.3.2 右单旋
2.3.3左右双旋
2.3.4 右左双旋
1.AVL树的概念
1. AVL树是最先发明的⾃平衡⼆叉查找树,AVL是⼀颗空树,或者具备下列性质的⼆叉搜索树:它的左右⼦树都是AV树,且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树,通过控制⾼度差去控制平衡。
2. AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家,他们在1962年的论⽂《An algorithm for the organization of information》中发表了它。
3. AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念,每个结点都有⼀个平衡因⼦,任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度,也就是说任何结点的平衡因⼦等于0/1/-1,AVL树并不是必须要平衡因⼦,但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡,就像⼀个⻛向标⼀样。
4. 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树,要求⾼度差不超过1,⽽不是⾼度差是0呢?0不是更好的平衡吗?画画图分析我们发现,不是不想这样设计,⽽是有些情况是做不到⾼度差是0的。
=》⽐如⼀棵树是2个结点,4个结点等情况下,⾼度差最好就是1,⽆法作为⾼度差是0
AVL树整体结点数量和分布和完全⼆叉树类似,⾼度可以控制在 logN ,那么增删查改的效率也可以控制在 O(logN ) ,相⽐⼆叉搜索树有了本质的提升。
2.AVL树的实现
2.1AVL树的结构
2.2AVL树的插入
2.2.1 AVL树插⼊⼀个值的⼤概过程
1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
2. 新增结点以后,只会影响祖先结点的⾼度,也就是可能会影响部分祖先结点的平衡因⼦,所以更新从新增结点->根结点路径上的平衡因⼦,实际中最坏情况下要更新到根,有些情况更新到中间就可以停⽌了,具体情况我们下⾯再详细分析。
3. 更新平衡因⼦过程中没有出现问题,则插⼊结束
4. 更新平衡因⼦过程中出现不平衡,对不平衡⼦树旋转,旋转后本质调平衡的同时,本质降低了⼦树的⾼度,不会再影响上⼀层,所以插⼊结束。(就是平衡因子的绝对值超过了1)
2.2.2平衡因子的更新
更新原则:
例子1:更新到10,平衡因子为2,子树不平衡,需要旋转
例子2:以3为根的子树高度不变,不会影响上一层,更新结束。
例子3:最坏更新到根节点
2.2.3 插⼊结点及更新平衡因⼦的代码实现
2.3旋转
2.3.1旋转的原则
1. 保持搜索树的规则(左孩子比父节点小,右孩子比父节点大)
2. 让旋转的树从不满⾜变平衡,其次降低旋转树的⾼度。
旋转总共分为四种,左单旋/右单旋/左右双旋/右左双旋。
2.3.2 右单旋
1. 本图1展⽰的是10为根的树,有a/b/c抽象为三棵⾼度为h的⼦树(h>=0),a/b/c均符合AVL树的要求。10可能是整棵树的根,也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树,
是⼀种概括抽象表⽰,他代表了所有右单旋的场景,实际右单旋形态有很多种,具体图2/图3/图4/图5进⾏了详细描述。
2. 在a⼦树中插⼊⼀个新结点,导致a⼦树的⾼度从h变成h+1,不断向上更新平衡因⼦,导致10的平衡因⼦从-1变成-2,10为根的树左右⾼度差超过1,违反平衡规则。10为根的树左边太⾼了,需要往右边旋转,控制两棵树的平衡。
3. 旋转核⼼步骤,因为5 < b⼦树的值 < 10,将b变成10的左⼦树,10变成5的右⼦树,5变成这棵树新的根,符合搜索树的规则,控制了平衡,同时这棵的⾼度恢复到了插⼊之前的h+2,符合旋转原
则。如果插⼊之前10整棵树的⼀个局部⼦树,旋转后不会再影响上⼀层,插⼊结束了。
2.3.3左单旋
1. 本图6展⽰的是10为根的树,有a/b/c抽象为三棵⾼度为h的⼦树(h>=0),a/b/c均符合AVL树的要求。10可能是整棵树的根,也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树,
是⼀种概括抽象表⽰,他代表了所有右单旋的场景,实际右单旋形态有很多种,具体跟上⾯左旋类似。
2. 在a⼦树中插⼊⼀个新结点,导致a⼦树的⾼度从h变成h+1,不断向上更新平衡因⼦,导致10的平衡因⼦从1变成2,10为根的树左右⾼度差超过1,违反平衡规则。10为根的树右边太⾼了,需要往左边旋转,控制两棵树的平衡。
3. 旋转核⼼步骤,因为10 < b⼦树的值 < 15,将b变成10的右⼦树,10变成15的左⼦树,15变成这棵树新的根,符合搜索树的规则,控制了平衡,同时这棵的⾼度恢复到了插⼊之前的h+2,符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树,旋转后不会再影响上⼀层,插⼊结束了。
2.3.3左右双旋
通过图7和图8可以看到,左边⾼时,如果插⼊位置不是在a⼦树,⽽是插⼊在b⼦树,b⼦树⾼度从h变成h+1,引发旋转,右单旋⽆法解决问题,右单旋后,我们的树依旧不平衡。右单旋解决的纯粹的左边⾼,但是插⼊在b⼦树中,10为跟的⼦树不再是单纯的左边⾼,对于10是左边⾼,但是对于5是右边⾼,需要⽤两次旋转才能解决,以5为旋转点进⾏⼀个左单旋,以10为旋转点进⾏⼀个右单旋,这棵树这棵树就平衡了。
图7和图8分别为左右双旋中h==0和h==1具体场景分析,下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析,另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树,因为
我们要对b的⽗亲5为旋转点进⾏左单旋,左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置不同,平衡因⼦更新的细节也不同,通过观察8的平衡因⼦不同,这⾥我们要分三个场景讨论。
场景1:h >= 1时,新增结点插⼊在e⼦树,e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦,引发旋转,其中8的平衡因⼦为-1,旋转后8和5平衡因⼦为0,10平衡因⼦为1。
场景2:h >= 1时,新增结点插⼊在f⼦树,f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦,引发旋转,其中8的平衡因⼦为1,旋转后8和10平衡因⼦为0,5平衡因⼦为-1。
场景3:h == 0时,a/b/c都是空树,b⾃⼰就是⼀个新增结点,不断更新5->10平衡因⼦,引发旋转,其中8的平衡因⼦为0,旋转后8和10和5平衡因⼦均为0。
2.3.4 右左双旋
跟左右双旋类似,下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析,另外我们需要把b⼦树的细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树,因为我们要对b的⽗亲15为旋转点进⾏右单
旋,右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同,平衡因⼦更新的细节也不同,通过观察12的平衡因⼦不同,这⾥我们要分三个场景讨论。
场景1:h >= 1时,新增结点插⼊在e⼦树,e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦,引发旋转,其中12的平衡因⼦为-1,旋转后10和12平衡因⼦为0,15平衡因⼦为1。
场景2:h >= 1时,新增结点插⼊在f⼦树,f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦,引发旋转,其中12的平衡因⼦为1,旋转后15和12平衡因⼦为0,10平衡因⼦为-1。
场景3:h == 0时,a/b/c都是空树,b⾃⼰就是⼀个新增结点,不断更新15->10平衡因⼦,引发旋转,其中12的平衡因⼦为0,旋转后10和12和15平衡因⼦均为0。
本期学习结束,谢谢大家支持!!!