专栏：Java数据结构秘籍
个人主页：手握风云
目录
一、二叉搜索树的回顾
二叉搜索树又称二叉排序树。当这棵树不为空时，如果左子树不为空，则左子树上所有节点的值均小于它的根节点的值；如果右子树不为空，则右子树上所有节点的值均大于它的根节点的值。当二叉搜索树进行中序遍历时，得到一个有序数组。
对二叉搜索树进行查找和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：；最差情况下，二叉搜索树退化为单支树，相当于在顺序表中寻找元素，其平均比较次数为：
。
二、AVL树
2.1. 概念
当二叉搜索树里的元素接近有序时，查找和删除效率低下。在1962年，苏联科学家G.M. Adelson-Velsky和E.M. Landis提出一种自平衡的二叉搜索树，AVL树：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树不为空树时具有以下性质：1.具有二叉搜索树的性质；2.每个节点的左右子树高度差（平衡因子）的绝对值不超过1；3.AVL树的每个子树也必须是AVL树。
如果一棵AVL树有n个节点，其高度可保持在，搜索时间复杂度
。
在AVL树中，平衡因子是每个节点的一个属性，用来衡量该节点的左右子树的高度差，定义为一个节点的左子树的高度减去它的右子树的高度。
2.2. 节点的定义
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;
}
}
}不是每棵树都必须有平衡因子，这只是其中的一种实现方式。
2.3. AVL 树的插入
AVL树的插入先按照二叉搜索树的插入方式，然后再根据平衡因子来进行调整。如果说整棵树为空，那么新插进入的结点则定义为根结点。
// 如果根节点为空，则创建一个新的节点作为根节点
TreeNode node = new TreeNode(val);
if (root == null) {
root = node;
return true;
}
当我们要插入值为10结点时，先定义一个cur引用指向root，当cur.val>val时，让cur引用指向当前结点的右孩子结点；当cur.val=val时，返回false；当cur.val<val时，让cur引用指向当前结点的左孩子结点。我们还需要定义一个p引用用来保存cur的上一个引用。
TreeNode parent = null;
TreeNode cur = root;
while (cur != null) {
// 如果当前节点的值小于要插入的值，则向右子树遍历
if (cur.val < val) {
parent = cur;
cur = cur.right;
// 如果当前节点的值等于要插入的值，则返回false
} else if (cur.val == val) {
return false;
// 如果当前节点的值大于要插入的值，则向左子树遍历
} else {
parent = cur;
cur = cur.left;
}
}
// 如果要插入的值大于父节点的值，则将新节点插入到父节点的右子树
if (parent.val < val) {
parent.right = node;
// 如果要插入的值小于父节点的值，则将新节点插入到父节点的左子树
} else {
parent.left = node;
}完成插入之后，结果就会如下图所示，此时这棵树就不平衡了。接下来就需要调节平衡因子
2.4. AVL树的旋转
当我们像上图一样插入之后，就需要修改平衡因子。当插入到右子树时，该子树的父亲节点的平衡因子增加；当插入到左子树时，该子树的父亲节点的平衡因子减少。
//调节平衡因子
while () {
if (cur == parent.right) {
parent.bf++;
} else {
parent.bf--;
}
}如果出现了下图这种情况，如果当前节点节点存在左孩子节点，当新节点插入到右子树时，此时父亲节点的平衡因子为0，当前树就平衡了，也不需要向上调整了。
如果出现了下图这种情况，整棵树本身是平衡的，但其中一个节点的平衡因子是-1或1，我们插入节点之后，修改了平衡因子为0，此时我们就不需要向上调节了。
//说明已经平衡了
if (parent.bf == 0) {
break;
//当前子树平衡，但整棵树不平衡，继续向上调整
} else if (parent.bf == 1 || parent.bf == -1) {
cur = parent;
parent = cur.parent;
} else {
}接下来又可以分两种情况：一种是当前父亲节点平衡因子为2，另一种是当前父亲节点平衡因子为-2，而孩子节点的平衡因子为1或者-1。
if (parent.bf == 2) {//右树高，需要降低右子树的高度
if (curt.bf == 1) {
} else if (cur.bf == -1) {
}
} else if (parent.bf == -2) {//左树高，需要降低左子树的高度
if (cur.bf == 1) {
} else if (cur.bf == -1) {
}- 右单旋
我们先定义这棵树的左孩子节点subL，再定义subL节点的右孩子节点subLR。先将父亲节点的左孩子引用指向subLR，再将subL的右孩子引用指向父亲节点，这样就可以将30这个节点置为新的父亲节点，最后原来的父亲节点的父亲引用指向新的父亲引用。
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
// 将parent节点的左子节点设置为subLR
parent.left = subLR;
// 将subL节点的右子节点设置为parent
subL.right = parent;
// 将subLR节点的父节点设置为parent
subLR.parent = parent;
// 将parent节点的父节点设置为subL
parent.parent = subL;
}但在旋转的时候需要注意，这棵树的父亲节点有可能是根节点，也有可能是左子树或者右子树。如果父亲节点本身就是根节点，那么直接将subL设置为根节点。如果这棵树是一个子树，则将subL设置为parent父亲节点的孩子节点。
// 如果parent节点是根节点，则将subL节点设置为根节点
if (parent == root) {
root = subL;
root.parent = null;
} else {
// 如果parent节点是其父节点的左子节点，则将subL节点设置为parent节点的父节点的左子节点
if (pParent.left == parent) {
pParent.left = subL;
// 如果parent节点是其父节点的右子节点，则将subL节点设置为parent节点的父节点的右子节点
} else if (pParent.right == parent) {
pParent.right = subL;
}
subL.parent = pParent;
}旋转完之后，还需要修改平衡因子。我们需要将subL节点和parent节点的平衡因子置为空，并且还需要判断subLR是否为空。
/**
* 右单旋
* @param parent
*/
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
// 将parent节点的左子节点设置为subLR
parent.left = subLR;
// 将subL节点的右子节点设置为parent
subL.right = parent;
//没有subLR节点
if (subLR != null) {
subLR.parent = parent;
}
// 将subLR节点的父节点设置为parent
// 获取parent节点的父节点
TreeNode pParent = parent.parent;
// 将parent节点的父节点设置为subL
parent.parent = subL;
// 如果parent节点是根节点，则将subL节点设置为根节点
if (parent == root) {
root = subL;
root.parent = null;
} else {
// 如果parent节点是其父节点的左子节点，则将subL节点设置为parent节点的父节点的左子节点
if (pParent.left == parent) {
pParent.left = subL;
// 如果parent节点是其父节点的右子节点，则将subL节点设置为parent节点的父节点的右子节点
} else if (pParent.right == parent) {
pParent.right = subL;
}
subL.parent = pParent;
}
subL.bf = 0;
parent.bf = 0;
}- 左单旋
左单旋与右单旋的思路一致，同样需要定义节点引用，修改指向，将其变为平衡树，并且也要修改平衡因子。
/**
* 左单旋
* @param 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;
if (root == parent) {
root = subR;
root.parent = null;
} else {
if (pParent.left == parent) {
pParent.left = subR;
} else if (pParent.right == parent) {
pParent.right = subR;
}
subR.parent = pParent;
}
subR.bf = 0;
parent.bf = 0;
}旋转完之后，当不再遇到平衡因子为2或-2时，此时说明已经平衡了，与此同时parent节点也不为空。
- 左右双旋
我们发现前两个单旋的平衡因子都是同号的，但还有两种情况就是平衡因子出现异号的情况，如下图这种情况，我们无论是左旋还是右旋都无法达到我们想要的平衡效果。
我们先将30这个节点进行左旋，再将整棵树进行右旋，才能达到我们想要的效果。旋转完之后，记得修改平衡因子。
以上为subLR的平衡因子为-1时，还需注意当subLR的平衡因子为1时的平衡因子。
/**
* 左右双旋
* @param parent
*/
private void rotateLR(TreeNode parent) {
// 获取左子节点
TreeNode subL = parent.left;
// 获取左子节点的右子节点
TreeNode subLR = subL.right;
// 获取右子节点的平衡因子
int bf = subLR.bf;
// 左旋左子节点
rotateLeft(parent.left);
// 右旋父节点
rotateRight(parent);
// 如果右子节点的平衡因子为-1
if (bf == -1) {
subL.bf = 0;
subLR.bf = 0;
parent.bf = 1;
// 如果右子节点的平衡因子为1
} else if (bf == 1) {
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}- 右左双旋
/**
* 右左双旋
* @param parent
*/
private void rotateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
// 右旋右子节点
rotateRight(parent.right);
// 左旋父节点
rotateLeft(parent);
// 如果右子节点的左子节点的平衡因子为1
if (bf == 1) {
subR.bf = 0;
subRL.bf = 0;
parent.bf = -1;
// 如果右子节点的左子节点的平衡因子为-1
} else if (bf == -1) {
subR.bf = 0;
subRL.bf = 1;
parent.bf = 0;
}
}2.5. AVL树的验证
要想验证当前树是否为AVL树：1. 该树是否为二叉搜索树；2. 高度差的绝对值不超过1。判断二叉搜索树，只需中序遍历的结果是否有序；求高度差，递归分别获取左右子树的高度。但下面的代码是有问题的，如果平衡因子本身就是错误的，我们无法判断出哪个平衡因子有问题。所以我们还需要加个判断，子树的高度差是否等于平衡因子。
/**
* 验证是否为二叉搜索树
* @param root
*/
private void InOrder(TreeNode root) {
if (root == null) {
return;
}
InOrder(root.left);
System.out.println(root.val + " ");
InOrder(root.right);
}
/**
* 计算二叉树高度
* @param root
* @return
*/
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;
}
/**
* 验证是否为AVL树
* @param root
* @return
*/
private boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftH = Height(root.left);
int rightH = Height(root.right);
return Math.abs(leftH - rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}修改后的代码：
/**
* 验证是否为二叉搜索树
* @param root
*/
private void InOrder(TreeNode root) {
if (root == null) {
return;
}
InOrder(root.left);
System.out.println(root.val + " ");
InOrder(root.right);
}
/**
* 计算二叉树高度
* @param root
* @return
*/
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;
}
/**
* 验证是否为AVL树
* @param root
* @return
*/
private 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("平衡因子异常");
return false;
}
return Math.abs(leftH - rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}public class Test {
public static void main(String[] args) {
int[] array = new int[]{4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
AVLTree avlTree = new AVLTree();
for (int i = 0; i < array.length; i++) {
avlTree.insert(array[i]);
}
System.out.println(avlTree.isBalanced(avlTree.root));
}
}
2.6. AVL的性能分析
因为AVL树始终保持着高度平衡。这意味着树的高度始终保持在对数级别，即 O(logN)，其中 N 是树中节点的数量。以下是AVL树各项操作的性能概览：
- 查找 (Search): O(log N)
- 插入 (Insertion): O(log N)
- 删除 (Deletion): O(log N)
优点：高效的查找性能；适用于内存访问开销较高的场景。缺点：插入和删除操作开销较大；额外的存储空间。