目录
一、什么是AVL树
在了解什么是AVL树之前，我们先回顾二叉搜索树的概念
二叉搜索树（二叉排序树），它或是一棵空树，或具有以下性质：
1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点
3. 它的左右子树也分别是二叉搜索树
根据二叉搜索树的性质，我们可以发现：
1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点是树中最大的节点
2. 若采用中序遍历二叉搜索树，则可得到一个有序的序列
二叉搜索树最主要的作用就是用于进行查询：
当二叉搜索树是一颗完全二叉树时：
其查询的平均查找次数为:
而当二叉搜索树是一颗单支树时：
其平均查找次数为：
由此可见二叉搜索树的平均查找次数与二叉搜索树的深度成正相关，即深度越深，比较查找的次数越多。而当其是单支树时，二叉搜索树的性能就降低了，此时，能否对其进行改进，使其无论怎样插入，都能够使二叉搜索树的性能最佳？
AVL树的出现解决了这个问题。
ALV树（也就是平衡二叉查找树，简称平衡二叉树）或是一颗空树，或具有以下性质：
1. 它的左右子树高度之差（简称平衡因子）的绝对值不超过1
2. 它的左右子树都是AVL树
由AVL树的性质，我们可以发现：
1. 每当向AVL树中插入新的节点时，都要保证每个节点的左右子树高度差（平衡因子）的绝对值不超过1（当超过时需要对树中的节点进行调整，即降低树的高度，从而减少平均搜索长度）
2. 若一颗AVL树有n个节点，它的高度能够保持在，因此，其搜索的时间复杂度为O(
二、AVL树的实现
AVL树的节点
在这里，我们通过一个内部类来实现AVL树节点的定义，通过维护节点的左孩子、右孩子和父亲节点来实现AVL树，同时定义一个平衡因子bf，通过平衡因子来判断是否需要调整树中节点。同时，我们需要定义根节点：
public class AVLTree {
static class TreeNode{
public int val;//节点的值
public int bf;//平衡因子
public TreeNode left;//左孩子
public TreeNode right;//右孩子
public TreeNode parent;//父亲节点
public TreeNode(int val){
this.val = val;
}
}
public TreeNode root;//根节点
}当前节点的平衡因子 = 右子树的高度 – 左子树的高度
AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此，我们可以将AVL树的插入过程分为两步：
1. 插入新的节点
2. 调整节点的平衡因子
现在我们对新的节点进行插入：
1. 当AVL树为空时，插入的节点即为根节点
2. AVL树不为空，则寻找新节点的插入位置
如何寻找新节点的插入位置？
若新节点node的值val > 当前节点cur的值val，则在cur的右子树寻找插入位置；
若node.val < cur.val，则在cur的左子树寻找插入位置；
若node.val = cur.val，则AVL树中已有该节点，插入失败，直接返回false
在找到插入位置后，我们需要知道其父亲节点，从而进行插入，因此在查找过程中，我们可以定义当前节点cur的父亲节点parent，用于最后进行插入新节点：
//节点的插入
public boolean insert(int val){
TreeNode node = new TreeNode(val);
//若根节点为空，则直接将插入为根节点
if(root == null){
root = node;
return true;
}
//根节点不为空，查找其插入位置
TreeNode parent = null;
TreeNode cur = root;
while (cur != null){
if(cur.val < val){
parent = cur;
cur = cur.right;
}else if(cur.val > val){
parent = cur;
cur = cur.left;
}else{
return false;//若已有该节点，则插入失败，直接返回false
}
}
//将节点插入
node.parent = parent;
cur = node;
} AVL树的旋转
在插入新的节点之后，此时AVL树中某些节点的平衡因子会发生改变，因此我们需要对平衡因子进行修改，而在插入新节点后，节点的平衡因子的绝对值可能超过1，此时我们需要对节点进行调整
我们首先对平衡因子进行修改：
在插入新节点时，我们定义了其父亲节点parent，由于在这里平衡因子 = 右子树的高度 – 左子树的高度
因此，若新插入的节点在parent的左子树，则其平衡因子 -1；而若新插入的节点在parent的右子树，则平衡因子 +1
在修改完当前平衡因子后，我们需要对当前平衡因子进行检查，判断其是否符合条件：
1. 若修改后的平衡因子 = 0，则表明未修改时parent的平衡因子bf = 1 或 -1，在插入后被调整成为0，此时子树parent已经平衡了，且其高度并未发生改变，不会影响上面节点的平衡因子，因此不用再继续向上判断
2. 若修改后的平衡因子 = 1 或 -1，则表明未修改时parent的平衡因子bf = 0，在插入之后被调整成 1 或 -1，此时子树parent的高度增加，上面节点的平衡因子也会被影响，因此需要继续向上更新平衡因子
3. 若修改后的平衡因子的绝对值 > 1，此时则需要对AVL树的节点进行调整，重新使其平衡
在这里，我们通过旋转来调整节点的平衡因子，AVL树的旋转分为四种情况：
右单旋
（1）新节点插入较高左子树的左侧->右单旋
当新节点插入较高左子树的左侧时：
此时 patent.bf = -2, cur.bf = -1，要想办法降低左子树的高度，因此对其进行调整：
将对于以parent 为根的子树：
将cur作为其根；parent作为cur的右子树；cur原右子树（若有的话）作为parent的左子树，
这样重新调整后，cur和parent的平衡因子都被调整为0，此时以cur为根的子树已经平衡
因此，我们调整的步骤为：
我们设parent的左孩子cur为subL，cur的右孩子为subLR（因为要考虑cur的右孩子不存在的情况）
1. 将parent的左孩子更新为subLR，将subLR的父亲节点更新为parent
注：此时要考虑subLR为空的情况，若subLR为空，则不需要更新
2. 将subL的右孩子更新为parent，将parent的父亲节点更新为subL
注：在更新parent的父亲节点时，我们首先要将parent的父亲节点pParent保存起来，因为我们需要将subL的父亲节点更新为parent的父亲节点
3. 更新subL的父亲节点，
若parent原为根节点，此时需要将根节点更新为subL，同时将subL的父亲节点更新为null；
若parent原不为根节点，则更新subL的父亲节点为pParent，同时需要更新pParent的孩子节点，此时需要判断parent为pParent的左孩子还是右孩子，并更新
右单旋代码：
//右单旋
private void rotateRight(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
parent.left = subLR;
if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
subLR.parent = parent;
}
subL.right = parent;
//在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
TreeNode pParent = parent.parent;
parent.parent = subL;
//判断subL是否被修改为根节点
if(parent == root){
root = subL;
root.parent = null;
}else {
subL.parent = pParent;
//判断是左子树还是右子树
if(pParent.left == parent){
pParent.left = subL;
}else {
parent.right = subL;
}
}
//修改平衡因子
subL.bf = 0;
parent.bf = 0;
}左单旋
新节点插入较高右子树的右侧->左单旋
左单旋与右单旋类似：
当新的节点插入到较高右子树的右侧时：
此时 parent.bf = 2, cur.bf = 1，要想办法降低右子树的高度，对以parent为根的子树进行调整：
设parent的右孩子cur为subR，subR的左孩子为subRL（要考虑subR的左孩子为空的情况）
1. 将parent的右孩子更新为subRL，将subRL的父亲节点更新为parent（若subRL不为空）
2. 将subR的左孩子更新为parent，保存parent的父亲节点pParent，再更新parent的父亲节点为subR
3. 更新subR的父亲节点，若parent原为根节点，则更新根节点为subR，并将其父亲节点更新为null；若parent原不为根节点，则更新subR的父亲节点为pParent，判断parent原为pParent的左孩子还是右孩子，并将subR更新为pParent的孩子节点
左单旋代码：
//左单旋
private void rotateLeft(TreeNode parent){
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
subRL.parent = parent;
}
subR.left = parent;
//在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
TreeNode pParent = parent.parent;
parent.parent = subR;
//判断subR是否被修改为根节点
if(parent == root){
root = subR;
root.parent = null;
}else {
//判断是其左子树还是右子树
if(pParent.left == parent){
pParent.left = subR;
}else{
pParent.right = subR;
}
subR.parent = pParent;
}
//修改平衡因子
subR.bf = 0;
parent.bf = 0;
}左右双旋
新节点插入较高左子树的右侧->左右双旋（先左单旋再右单旋）
当新的节点插入较高左子树的右侧时：
此时 parent.bf = -2, cur.bf = 1，此时对于以parent为根的子树，无论是进行右单旋，还是进行左单旋，都不能使其平衡。因此，此时不能只进行一次旋转，而需要进行两次旋转：
首先，我们需要对以cur为根的子树进行一次左单旋：
然后再对以parent为根的子树进行一次右单旋：
此时调整后的子树达到平衡状态，由于进行的左单旋和右单旋会更改其中节点的平衡因子，因此我们需要对被修改的平衡因子进行重新调整：
平衡因子被修改的节点有：parent、parent的左孩子subL、subL的右孩子subLR
它们的平衡因子都被修改为0，
然而经过两次旋转后，它们的平衡因子并不都为0
通过观察我们发现，当subLR的平衡因子原为-1时，经过调整后，parent的平衡更新为1
当subLR的平衡因子原为1时，经过调整后，subL的平衡因子被更新为-1：
当subLR的平衡因子原为0时，经过调整后，parent、subL和subLR的平衡因子都为0：
因此，我们根据subLR原平衡因子来调整旋转两次之后的平衡因子
为什么subLR的平衡因子不同，两次旋转后的平衡因子也不同呢？
当subLR的平衡因子为-1时，经过一次左单旋，subRL的左子树变为subR的右子树，由于subR的平衡因子为1，经过这次左旋后，其右子树的高度减一（少了subRL），此时subR的平衡因子变为0，且subRL变为subR的父亲节点。
当subLR变为subR的父亲节点时，其平衡因子变为 -2 ，这是因为subRL的原平衡因子为-1，经过一次左旋后，其左子树高度增加1（增加了subR），右子树高度不变，因此平衡因子变为 -2。
而parent的平衡因子不变，仍是 -2，这是因为在经过一次左单旋后，其右子树高度不变，虽其左孩子变为了subRL，但其高度未改变，因此parent的平衡因子不变
其过程更新过程如下图：
此时，我们假设subLR的左子树高度为m，由于其平衡因子为-2，则subLR的右子树高度为m-2，而parent的左子树高度为m+1，parent的右子树高度为m-1
当进行一次右旋后，由于subR的左右子树不变，因此其平衡因子仍为0
而parent变为subLR的右子树，且其左子树变为subLR的右子树，parent的右子树高度未改变，任为m – 1，而parent的左子树变为subLR的右子树，因此其高度变为m-2，则parent子树的高度为m-1，平衡因子变为 1
subLR的左子树为改变，高度任为m，而右子树变为以parent为根的子树，parent子树的高度为m-1，再加上parent，则为m，因此subLR的平衡因子变为0
当subLR的平衡因子为1和为0时也是同样的分析过程，大家可自行进行分析，这里就不再进行分析了
左右双旋代码：
//左右双旋
private void rotateLR(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
//记录subLR平衡因子
int bf = subLR.bf;
rotateLeft(parent.left);//先左旋
rotateRight(parent);//再右旋
//修改平衡因子
if(bf == -1){
parent.bf = 1;
}else if(bf == 1){
subL.bf = -1;
}
}右左双旋
新节点插入较高右子树的左侧->右左双旋（先右单旋再左单旋）
右左双旋与左右双旋的情况类似
当新节点插入较高右子树的左侧时：
此时 parent.bf = 2, cur.bf = -1，仍要进行两次旋转，才能将以parent为根的子树调整为平衡的子树
此时要先对其进行右旋：
再对其进行左旋：
最后，我们再根据原subRL的平衡因子对平衡因子对其修改：
当subRL原平衡因子为1时，更新后的parent的平衡因子为-1
当subRL原平衡因子为-1时，更新后的subR的平衡因子为1
当subRL原平衡因子为0时，更新后parent、subR和subRL的平衡因子都为0
右左双旋的代码为：
//右左双旋
private void rotateRL(TreeNode parent){
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
//记录subRL的平衡因子
int bf = subRL.bf;
rotateRight(subR);//先右旋
rotateLeft(parent);//再左旋
//修改平衡因子
if(bf == 1){
parent.bf = -1;
}else if(bf == -1){
subR.bf = 1;
}
}由上述四种旋转过程可知：经过旋转后，都能使节点的平衡因子到达平衡，此时无需再向上调整，因此修改平衡因子的代码为：
//修改平衡因子
//平衡因子 = 右子树高度 - 左子树高度
while (parent != null){
//判断cur是parent的左还是右，从而决定其平衡因子是++还是--
if(cur == parent.right){
parent.bf++;
}else {
parent.bf--;
}
//检查当前平衡因子 判断是否符合条件（-1 0 1）
if(parent.bf == 0){
//已经平衡
break;
}else if(parent.bf == 1 || parent.bf == -1){
//需要继续向上判断是否需要修改平衡因子
cur = parent;
parent = cur.parent;
}else {
//不平衡，需要进行旋转，使其平衡
if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
if(cur.bf == 1){
//直接左旋
rotateLeft(parent);
}else {
//右左双旋
rotateRL(parent);
}
}else {//左树高，需要右旋，从而降低左树高度
if(cur.bf == -1){
//直接右旋
rotateRight(parent);
}else {
//左右双旋
rotateLR(parent);
}
}
//旋转之后，平衡
break;
}
}AVL树的验证
在我们插入节点后，如何验证我们创建出的树是否是AVL树？
AVL树是高度平衡的二叉搜索树，其平衡因子的绝对值不超过1，能否通过节点的平衡因子来验证？
不能通过平衡因子来验证，因为平衡因子是我们通过计算得出的，若我们在计算时出现错误，那我们通过平衡因子验证的结果也是错误的（例如在左右双旋时，未在最后修改平衡因子，则此时计算的平衡因子不完全正确）
那么我们应该如何进行验证呢？
首先，AVL树也是二叉搜索树，二叉搜索树中序遍历的结果是有序的，因此我们可以通过中序遍历来验证
public void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}其次，AVL树节点的平衡因子绝对值不超过1，即左右子树的高度差不超过1，我们可以通过计算左右子树的高度差来判断树是否是高度平衡的，同时，通过比较计算出的高度差和平衡因子，我们也可以验证当前节点的平衡因子是否正确
private int height(TreeNode root) {//计算子树高度
if(root == null) return 0;
int leftH = height(root.left);
int rightH = height(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftH = height(root.left);
int rightH = height(root.right);
//判断平衡因子是否正确
if(rightH-leftH != root.bf) {
System.out.println("节点："+root.val+" 平衡因子异常");
return false;
}
//判断左右子树高度差绝对值是否不超过1
return Math.abs(leftH-rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}完整代码：
public class AVLTree {
static class TreeNode{
public int val;//节点的值
public int bf;//平衡因子
public TreeNode left;//左孩子
public TreeNode right;//右孩子
public TreeNode parent;//父亲节点
public TreeNode(int val){
this.val = val;
}
}
public TreeNode root;//根节点
//节点的插入
public boolean insert(int val) {
TreeNode node = new TreeNode(val);
//若根节点为空，则直接将插入为根节点
if (root == null) {
root = node;
return true;
}
//根节点不为空，查找其插入位置
TreeNode parent = null;
TreeNode cur = root;
while (cur != null) {
if (cur.val < val) {
parent = cur;
cur = cur.right;
} else if (cur.val > val) {
parent = cur;
cur = cur.left;
} else {
return false;//若已有该节点，则插入失败，直接返回false
}
}
//将节点插入
node.parent = parent;
cur = node;
//修改平衡因子
//平衡因子 = 右子树高度 - 左子树高度
while (parent != null){
//判断cur是parent的左还是右，从而决定其平衡因子是++还是--
if(cur == parent.right){
parent.bf++;
}else {
parent.bf--;
}
//检查当前平衡因子 判断是否符合条件（-1 0 1）
if(parent.bf == 0){
//已经平衡
break;
}else if(parent.bf == 1 || parent.bf == -1){
//需要继续向上判断是否需要修改平衡因子
cur = parent;
parent = cur.parent;
}else {
//不平衡，需要进行旋转，使其平衡
if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
if(cur.bf == 1){
//直接左旋
rotateLeft(parent);
}else {
//先右旋，再左旋
rotateRL(parent);
}
}else {//左树高，需要右旋，从而降低左树高度
if(cur.bf == -1){
//直接右旋
rotateRight(parent);
}else {
//先左选，再右旋
rotateLR(parent);
}
}
//经过旋转之后，就平衡
break;
}
}
return true;
}
//左单旋
private void rotateLeft(TreeNode parent){
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
subRL.parent = parent;
}
subR.left = parent;
//在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
TreeNode pParent = parent.parent;
parent.parent = subR;
//判断subR是否被修改为根节点
if(parent == root){
root = subR;
root.parent = null;
}else {
//判断是其左子树还是右子树
if(pParent.left == parent){
pParent.left = subR;
}else{
pParent.right = subR;
}
subR.parent = pParent;
}
//修改平衡因子
subR.bf = 0;
parent.bf = 0;
}
//右单旋
private void rotateRight(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
parent.left = subLR;
if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
subLR.parent = parent;
}
subL.right = parent;
//在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
TreeNode pParent = parent.parent;
parent.parent = subL;
//判断subL是否被修改为根节点
if(parent == root){
root = subL;
root.parent = null;
}else {
subL.parent = pParent;
//判断是左子树还是右子树
if(pParent.left == parent){
pParent.left = subL;
}else {
parent.right = subL;
}
}
//修改平衡因子
subL.bf = 0;
parent.bf = 0;
}
//左右双旋
private void rotateLR(TreeNode parent){
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
//记录subLR平衡因子
int bf = subLR.bf;
rotateLeft(parent.left);//先左旋
rotateRight(parent);//再右旋
//修改平衡因子
if(bf == -1){
parent.bf = 1;
}else if(bf == 1){
subL.bf = -1;
}
}
//右左双旋
private void rotateRL(TreeNode parent){
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
//记录subRL的平衡因子
int bf = subRL.bf;
rotateRight(subR);//先右旋
rotateLeft(parent);//再左旋
//修改平衡因子
if(bf == 1){
parent.bf = -1;
}else if(bf == -1){
subR.bf = 1;
}
}
//验证
public void inorder(TreeNode root) {//中序遍历
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
private int height(TreeNode root) {//计算子树高度
if(root == null) return 0;
int leftH = height(root.left);
int rightH = height(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftH = height(root.left);
int rightH = height(root.right);
//判断平衡因子是否正确
if(rightH-leftH != root.bf) {
System.out.println("节点："+root.val+" 平衡因子异常");
return false;
}
//判断左右子树高度差绝对值是否不超过1
return Math.abs(leftH-rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
}
三、AVL树的性能分析
AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右子树高度差的绝对值都不超过1，这样能够保证查询时的高效，即查询的时间复杂度为O（）。但当对AVL树进行一些结构的修改操作时，性能就会比较低下（在插入时为了保持其绝对平衡，就需要进行旋转）。因此，若需要一种查询高效且有序的数据结构，且数据的个数为静态的（不改变），可以考虑使用AVL树，但若是其经常进行修改，就不太适合使用AVL树。
版权声明：本文为博主作者：楠枬原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/2301_76161469/article/details/135478292
