简介
AVL树的引入是因为BST
在极端的情况下,会退化为链表
,那么查找的时间从$O(logN)$ —-> $O(N)$
AVL树是一种自平衡的二叉树,定义如下
- BST
- 左、右子树高度差的绝对值不超过1(平衡因子Balance Factor)
空树、左右子树都是AVL

AVL树.png
插入&旋转
三节点单旋转
左旋

AVL_左旋.png
右旋

AVL_右旋.png
三节点双旋转
LR旋转

AVL_LR.png
RL旋转
同理
什么时候需要旋转
插入关键字key后,节点p的平衡因子由原来的1或者-1,变成了2或者-2,则需要旋转;只考虑插入key到左子树left的情形,即平衡因子为2
情况1:key<left.key, 即插入到left的左子树,需要进行单旋转,将节点p右旋
情况2:key>left.key, 即插入到left的右子树,需要进行双旋转,先将left左旋,再将p右旋
插入到右子树right、平衡因子为-2,完全对称
情况1

AVL_插入_情况1.png
情况2

AVL_插入_情况2_1.png
删除
类似插入,假设删除了p右子树的某个节点,引起了p的平衡因子d[p]=2,分析p的左子树left,三种情况如下:
- 情况1:left的平衡因子d[left]=1,将p右旋
- 情况2:left的平衡因子d[left]=0,将p右旋
- 情况3:left的平衡因子d[left]= -1,先左旋left,再右旋p
删除左子树,即d[p]= -2的情形,与d[p]=2对称
情况1

AVL_删除_情况1.png
情况2

AVL_删除_情况2.png
情况3

AVL_删除_情况3.png
面试
排序数组(链表)转AVL
108. Convert Sorted Array to Binary Search Tree
109. Convert Sorted List to Binary Search Tree
判断是否为平衡二叉树
LeetCode 110. Balanced Binary Tree
相关题目会持续添加