目录
前言
二叉搜索树可以帮助我们以极高的效率查找(理想情况下是logn)，但是当在极端情况下，比如当树中的节点值是有序的时，二叉搜索树会变成一个单枝树，相当于一个链表，于是乎为了让树更接近与一个完全二叉树，想着当向二叉搜索树中插入新节点后，让每个节点的左右子树高度差的绝对值不超过1就可以降低树的高度从而提高效率，于是就有了AVL树。
AVL树的特点
- 每个节点的左右子树都是AVL树
- 左右子树高度差(平衡因子)的绝对值不超过1
AVL树的插入
节点的定义
static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public int bf;//平衡因子
public TreeNode parent;
public TreeNode(int val) {
this.val = val;
}
}//平衡因子=右子树高度-左子树高度
情况分析
因为AVL树也是二叉搜索树，所以先按照二叉搜索树的方式插入一个节点cur，但是当cur被插入后，其父节点parent的平衡因子必定会发生变化(左右子树高度差必定发生变化)，所以每次插入节点后都需要更新平衡因子，并且检查AVL树的结构是否被破坏。情况可以分为以下几种
cur插入之前parent的平衡因子会有三种可能'-1' ,'0' ,'1'
- 当cur插入到parent的左边时parent的平衡因子-1
- 当cur插入到parent的右边时parent的平衡因子+1
cur插入之后parent的平衡因子可能会有五种可能‘-1’，‘+1’，‘0’，‘-2’，‘+2’
- 如果cur插入后parent的平衡因子是0，说明插入之前它的平衡因子是正负1，所以插入后才可能被调整为0，此时cur成功插入
- 如果cur插入后parent的平衡因子是正负1，说明插入之前它的平衡因子是0，所以插入后才可能被调整为正负1，此时以parent为根的树高度增加了，上面节点的平衡因子可能会被打破所以需要继续向上更新
- 如果cur插入后parent的平衡因子是正负2，则说明以parent为根的树不符合AVL树的性质，需要对其进行调整，既旋转
插入节点
TreeNode node = new TreeNode(val);
//如果根节点为空直接插入
if (root == null) {
root = node;
return true;
}
TreeNode parent = null;
TreeNode cur = root;
while (cur != null) {
if (val > cur.val) {
parent = cur;
cur = cur.right;
} else if (val < cur.val) {
parent = cur;
cur = cur.left;
} else {
return false;
}
}
//cur == null
if (val > parent.val) {
parent.right = node;
} else if (val < parent.val) {
parent.left = node;
}调整parent的平衡因子
//调整
cur = node;
node.parent = parent;
while (parent != null) {
//如果cur是父节点的右孩子，父节点的平衡因子就加一，否则减一
if (cur == parent.right) {
parent.bf++;
} else {
parent.bf--;
}
//判断平衡因子
if (parent.bf == 0) {
//已经平衡
break;
} else if (parent.bf == 1 || parent.bf == -1) {
//继续向上调整
cur = parent;
parent = cur.parent;
} else {
if (parent.bf == 2) {//右树高，需要降低右树高度(说明cur插到了parent的右边)
if (cur.bf == 1) {
//左单旋
} else if (cur.bf == -1) {
//右左双旋
}
//左树高，需要降低左树高度
} else {//parent.bf == -2(说明cur插到了parent的左边)
if (cur.bf == -1) {
//右单旋
} else if (cur.bf == 1) {
//左右双旋
}
}
break;
}
}AVL树的旋转
右单旋
当新节点插入较高左子树的左侧
上图是一个简单的右旋，当新节点10插入到30的左子树时(这里是左子树)，破坏了avl树的平衡节点50的平衡因子变成-2，表示左子树比右子树高2，所以我们需要降低左子树，提高右子树。既将50节点向右旋转到30节点的左边(因为50比三十大，只能在30的右边)，此时这颗AVL树就平衡了(别忘了修改平衡因子bf)
但是实际插入中的AVL树的结构可能不会和上图这样简单比如：
- 30的右边可能已经有节点了
0是新插入的节点插到了30的左子树的左侧，破坏了AVL树的平衡，使50节点的平衡因子变成-2，所以和刚刚一样我们需要降低左树，抬高右树，我们让50节点向右旋转，但是此时30节点的右边已经有了一个节点(也可能是30的右子树的根)，不过这个节点一定是大于30小于50的，所以我们只需要将这个节点放到50节点的左边，然后再将50节点放到30节点的右边即可，最后修改平衡因子。
- 50可能是其他节点的左右子树或者根节点
如果50是根节点那么当旋转完成后要更新根节点，如果50是其父节点的左孩子，那么要让30节点变成50原父节点的左孩子，右孩子则相反
代码
public void rotateRight(TreeNode parent) {
TreeNode pParetn = parent.parent;//记录parent的父节点
TreeNode subL = parent.left;//parent的左孩子
TreeNode subLR = subL.right;//parent的左孩子的右孩子
parent.left = subLR;
if (subLR != null) {
subLR.parent = parent;
}
subL.right = parent;
parent.parent = subL;
//检查当前parent是不是根节点
//是根节点的话直接让subL为根节点
if (parent == root) {
root = subL;
root.parent = null;
} else {//不是根节点，就判断parent是其父节点的左孩子还是右孩子
if (parent == pParetn.left) {//parent是左孩子，就让subL也是左孩子
pParetn.left = subL;
} else {
pParetn.right = subL;
}
subL.parent = pParetn;
}
subL.bf = 0;
parent.bf = 0;
}首先先标记右旋所需要的节点，然后开始右旋，过程和前文一样
- 将subLR作为parent的左孩子(就算subLR为空也无所谓)
- 判断subL是否有右孩子(subLR) ，有的话就令subLR的父节点位parent
- 让subL的右节点为parent
- 让parent的父节点为subLR
- 旋转完成后判断parent是否是根节点是的话，更新根节点，有父节点的话则让subL为parent父节点的孩子
- 最后修改平衡因子
右旋代码既图解
左单旋
当新节点插入较高右子树的右侧
左单旋的方法和右单旋一样，只是方向不一样，具体过程参考右单旋
代码及图解
private void rotateLeft(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
if (subRL != null) {
subRL.parent = parent;
}
TreeNode pParent = parent.parent;
parent.parent = subR;
//检查当前parent是不是root
if (parent == root) {
root = subR;
root.parent = null;
} else {//不是root
if (pParent.right == parent) {
pParent.right = subR;
} else {
pParent.left = subR;
}
subR.parent = pParent;
}
parent.bf = 0;
subR.bf = 0;
}左旋
- 首先先标记左旋所需要的节点，然后开始左旋
- 将subRL作为parent的右孩子
- 判断subR的左孩子是否为空，如果不为空则令subR的左孩子(subRL)的父节点为parent
- 令subR的左孩子为parent
- 令parent的parent为subR
- 旋转完成后判断parent是否是根节点是的话，更新根节点，有父节点的话则让subR为parent父节点的孩子
- 最后修改平衡因子
左右双旋
新节点插入较高左子树的右侧
这种情况无法通过直接左旋或者右旋使树平衡，需要先左旋再右旋，通过左旋把树变成左子树较高的情况然后再右旋
可以看到只是右旋达不到平衡的结果
先左旋再右旋
private void rotateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
int bf = subLR.bf;
rotateLeft(parent.left);
rotateRight(parent);
if (bf == 1) {
subL.bf = 0;
subLR.bf = 0;
parent.bf = 1;
} else if (bf == -1) {
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}以上面的例子说明当bf==1时说明新节点插到45左边，bf==-1时说明新节点插到45右边
bf==-1时旋转结果
右左双旋
新节点插到较高右子树的左侧
private void rotateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
rotateRight(parent.right);
rotateLeft(parent);
if (bf == 1) {
parent.bf = -1;
subR.bf = 0;
subRL.bf = 0;
} else if (bf == -1) {
parent.bf = 0;
subR.bf = 1;
subRL.bf = 0;
}
}
总结
当新节点插入后如果树不平衡，既parent的平衡因子为-2或者2
1.parent的平衡因子为2，说明右树高
- 如果SubR(右子树)的平衡因子为1，说明新节点插入较高右子树的右侧，执行左单旋
- 如果SubR的平衡因子为-1，说明新节点插入到较高右子树的左侧，执行右左双旋
2.parent的平衡因子为-2，说明左树高
- 如果SubL的平衡因子为-1，说明新节点插入到了较高左子树的左边，执行有右选
- 如果SubL的平衡因子为1，说明新节点插入到了较高左子树的右边，执行左右双旋
验证AVL树
验证AVL树只需要判断每个节点的左右子树高度差的绝对值都小于一就行
public int height(TreeNode node) {
if (node == null) {
return 0;
}
int left = height(node.left);
int right = height(node.right);
return left > right ? left + 1 : right + 1;
}
public Boolean isbalanced(TreeNode root) {
if (root == null) {
return true;
}
//求左右子树高度
int left = height(root.left);
int right = height(root.right);
if (root.bf != right - left) {
return false;
}
return Math.abs(left - right) <= 1
&& isbalanced(root.left)
&& isbalanced(root.right);
}
public static void main(String[] args) {
int[] array = {17, 4, 8, 6, 17, 25, 17, 19, 10};
AVLTree avlTree = new AVLTree();
for (int i=0;i<array.length;++i){
avlTree.insert(array[i]);
}
boolean ret = avlTree.isbalanced(avlTree.root);
System.out.println(ret);
}综上，AVL树其实就是一个相对平衡的二叉搜索树，每个节点的左右子树高度差的绝对值都小于一，这样可以使其查找的时间复杂度稳定为O(logN)，但是也因为其在进行修改操作时比如插入删除，需要对树进行多次旋转，使其修改变得及其麻烦。所以，如果需要 一种查询高效且有序的数据结构，而且数据的个数为静态的(修改操作较少或不修改)，可以考虑AVL树，但一个结构经常修 改，就不太适合
以上就是博主对AVL树知识的分享，在之后的博客中会陆续分享有关数据结构的其他知识，如果有不懂的或者有其他见解的欢迎在下方评论或者私信博主，也希望可以多多支持博主！！🥰🥰