【黑皮书】 AVL树

目录

前言

一  AVL树的介绍

二  单旋转

二  双旋转 

总结

---

前言

AVL树的学习

---

一  AVL树的介绍

AVL树是带有平衡条件的二叉查找树，这个平衡条件要持续保持，而且必须保证树的深度为O(log(N))最简单的想法就是要求左右子树具有相同的高度

一棵AVL树是其每一个节点的左子树和右子树的高度相差1的二叉查找树，空树的高度定义为-1，在对树进行操作的时候，时间复杂度往往都是log(N)，但是这里复杂操作就是插入，为什么？因为你插入一个节点可能会破坏AVL树的特性，那么就要把性质恢复以后才认为这一步插入完成，事实上可以通过对树进行简单的修正来做到，这个就称为旋转

二  单旋转

什么时候需要单旋转？怎么进行单旋转？这都是我们要考虑的问题
1  什么时候需要单旋转？

类似于这种，我们不难发现这个左右子树都是相差为2的，x都是有问题的，因为它破坏了AVL树的平衡，这个时候我们需要用到旋转，但是是不是用到单旋转呢？我们可以发现出现问题的树都是在外面的，那么我们就要单旋转，因为出现问题的树在外侧，如果是在内测就不是单旋转了

2  怎么进行单旋转？ 

我们可以看我们出现问题的节点在哪里，这个时候我们就进行标记，然后进行对应的旋转，上面的图已经画的很详细啦，然后单旋转的出现情况的简图我已经滑倒情景1，2的旁边啦，我们可以看到这个是一条直线的，不是弯曲的

二  双旋转 

1  什么时候需要进行双旋转 

我们可以看到上面两个图，这个出现问题都是在内测的，那么就是需要进行双旋转的情况，旁边我也画了简图，用来表示出需要双旋转的情况，接下来我们就要去思考怎么进行双旋转了

2  怎么进行双旋转？

其实双旋转就是两次单旋转，这上面画了过程图，很容易理解

综上所述：单旋转的情况就是在外侧的时候，简化结构图是直线的时候就是进行单旋转
                  双旋转的情况就是在内测的时候，简化结构图是直线的时候就是进行双旋转
过程就是找到问题的根节点，然后进行根节点上面一个节点进行旋转，然后再把这个问题根节点的子树进行重新放置就可以处理掉这个情况

---

总结

今天主要讲解了AVL树的简介，还有插入的操作，操作分为插入到内测和插入到外侧的情况，下一讲将讲述具体的代码实现