type
status
summary
date
slug
tags
category
icon
password
前言：AVL树是一种非常重要的数据结构，值得我们去深度的去学习和解析，在学习AVL树之前，我们的查找方法就是1.暴力查找2.二分查找3.搜索二叉树，对于二分查找来说，他是有前提的，必须是有序的，并且在插入删除时候性能是非常差的，对于搜索二叉树来说正常情况下搜索二叉树性能是不错的，但是没有保障在极端情况下，搜索二叉树会变成链表，这样他的性能就会变得极差，那么怎么解决这个搜索二叉树不稳定的问题呢，这里就引入了AVL树
1.AVL树的概念
AVL树其实是对搜索二叉树的一种优化：当向搜索二叉树中插入新的节点的时候，如果能保证两个节点的左右子树的高度差不超过1（需要对书中的节点进行调整），既能降低树的高度，也能提高搜索二叉树的性能（垂直搜索长度）
其实AVL名字的来源是源自于他的两位作者
一般AVL树具有一下特征：
- 左右子树都是AVL树
- 左右子树高度差绝对值不超过1（右子树高度减去左子树高度）
对于满二叉树来说2^h - 1 = N(是总元素数量)
对于AVL树来说 2^h - x = N
X的范围就是[1,2^(h-1)-1]
直接上代码：
但是其实这里跟之前的搜索二叉树其实没有区别，那么怎么改才能让是的搜索二叉树成为AVL树能,其实可以看到在AVLTreeNode上面除了left和right还有一个parent，如何控制旋转呢—-旋转
其实每一个节点都有他自己的一个平衡因子，平衡因子就是等于右子树高度减去左子树高度，当平衡因子等于2或者-2的时候就1说明AVL树已经失去平衡了，对parent树进行旋转，使树平衡
其实这里的旋转都是在插入当中进行的，对于parent来说
1.新增在左，平衡因子减减
2.新增在右，平衡因子加加
3.更新后子树平衡因子为0说明子树平衡，不会影响parent，不用沿着root向上更新
4.更新后子树的平衡因子变为1或者-1说明子树高度变化会影响parent需要沿着root向上更新
5.如果更新后子树的平衡因子变为2或者-2说明子树失衡要对parent所在子树进行旋转，使其平衡
6.一路更新直到root，更新也会结束
2.AVL树-旋转
AVL树有几种旋转模式，思考一下，当parent→_buf为2的时候说明右子树高度太高了，那怎么旋转才能使得平衡因子恢复正常——其实就是将右子树中的中间的一个节点（其实就是cur）重新当作root，使得两边平衡，但是这个时候AVL树的难点就体现出来了，其实就是降低树的高度并且在旋转过程中使的其仍然保持搜索二叉树的特征——左小右大
（1）左单旋
接下里探讨，这里的插入时有几种情况
（2）右单旋
其实右单旋和左单旋是大差不差的都是一个道理
……………
这里用代码实现一下右旋转函数
(3)那么当插入的情况是插入到b下面，这个时候单旋是解决不了问题
这个时候就要引入一种新的旋转模式—双旋
其实双旋转的代码也很简单，只需要之前实现过的右旋转和左旋转就好
(4)平衡因子的更新
其实最难的不是旋转，而是平衡因子的更新，在3节点左插入或者右插入，这两种情况其实都是不一样的，想要将平衡因子更新，需要分析很多种的情况，并且左插入右插入都会影响平衡因子的更新
作者总结：AVL树到底是怎样使得这个搜索二叉树保持平衡，是如何旋转的能不能简洁的描述一下？？其实AVL树的本文实现平衡主要是（因为有一些AVL树不是使用平衡因子来进行判断异常然后旋转的）平衡因子衡量是否出现异常，然后进行旋转，旋转呢主要有四种情况
- 左左情况（LL）：在节点的左孩子的左子树上插入节点，导致不平衡。这时，需要进行右旋操作。
- 右旋：将不平衡节点的左孩子上升为新的根节点，原根节点变为新根节点的右孩子，新根节点的右孩子（如果有的话）变为原根节点的左孩子。
- 右右情况（RR）：在节点的右孩子的右子树上插入节点，导致不平衡。这时，需要进行左旋操作。
- 左旋：将不平衡节点的右孩子上升为新的根节点，原根节点变为新根节点的左孩子，新根节点的左孩子（如果有的话）变为原根节点的右孩子。
- 左右情况（LR）：在节点的左孩子的右子树上插入节点，导致不平衡。这时，需要先对不平衡节点的左孩子进行左旋，再对不平衡节点进行右旋。
- 右左情况（RL）：在节点的右孩子的左子树上插入节点，导致不平衡。这时，需要先对不平衡节点的右孩子进行右旋，再对不平衡节点进行左旋。
- Author:PytC
- URL:https://PytC.fun//article/example-5
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!