概念
当按顺序往二分搜索树中添加元素时,其会退化成链表,为了让树结构能够有自平衡性,科学家们定义了一种新的平衡树——AVL树,名字取自几个科学家姓名的首字母。
AVL树的一些基本特性:
第一点,满足二分搜索树所有性质;
第二点,带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。
感性认识
如下演算:
已知10 9 6数列 ,插入一个4;
已知10 9 6数列,以10为轴,左子树高度为2,右子树高度为0,差值大于1,即平衡因子大于1,判定该树为不平衡,其中10为<不平衡起始节点>,6为<不平衡节点>,且由于<以10为起始节点,在它左孩子的左孩子处发生了不平衡(LL)>,需进行<右单旋>让其恢复平衡
10
/
9
/
6
↓
9
/ \
6 10
旋转完成后插入一个4:
9
/ \
6 10
/
4
四种情况(LL\RR\LR\RL)
在第一个例子中,我们有了<不平衡起始节点>,<不平衡节点>, <…(LL)>,<右单旋>这么一些认识。接下来进行挨个举例。一波操作下来应该大家都理解了。
LL
见上面列出都例子。RR
旋转前
10
/
9 15
16
22
旋转后
10
/
9 16
/
15 22
已知10 9 15 16 22 数列,以15为轴,左子树高度为0,右子树高度为2,差值大于1,即平衡因子大于1,判定该树为不平衡,其中15为<不平衡起始节点>,22为<不平衡节点>,且由于<以15为起始节点,在它**右孩子的右孩子处**(RR)发生了不平衡>,需进行<左单旋>让其恢复平衡。
- LR
```java
旋转前
9
/
6
\
8
旋转中
9
/
8
/
6
旋转后
8
/ \
6 9
已知9 6 8 数列,以9为轴,左子树高度为2,右子树高度为0,差值大于1,即平衡因子大于1,判定该树为不平衡,其中9为<不平衡起始节点>,8为<不平衡节点>,且由于<以9为起始节点,在它左孩子的右孩子处(LR)发生了不平衡>,需进行<先左再右旋>让其恢复平衡。
- RL
旋转前
10
/\
9 15
\
22
/
16
旋转中
10
/\
9 15
\
16
\
22
旋转后
10
/\
9 16
/ \
15 22
已知10 9 15 16 22 数列,以15为轴,左子树高度为0,右子树高度为2,差值大于1,即平衡因子大于1,判定该树为不平衡,其中15为<不平衡起始节点>,16为<不平衡节点>,且由于<以15为起始节点,在它右孩子的左孩子处(RL)发生了不平衡>,需进行<先右后左旋>让其恢复平衡。
总结
- 确保该树是哥bst树
- 从最深节点往跟节点追溯进行旋转
- 4种情况 左左右单旋 you you
参考链接:
https://www.sohu.com/a/270452030_478315
https://www.jianshu.com/p/fa7db1bb2577