什么是 AVL 树
AVL 树是高度平衡的二叉树。它的特点是：AVL 树中任何节点的两个子树的高度最大差别为 1。
原文此处给出了两棵树的对比图（已丢失，据文字重绘）：左边的是 AVL 树，它的任何节点的两个子树的高度差别都 <=1；而右边的不是 AVL 树，因为 7 的两颗子树的高度相差为 2（以 2 为根节点的树的高度是 3，而以 8 为根节点的树的高度是 1）：
flowchart TD
subgraph avl["AVL 树: 各节点左右子树高度差 <= 1"]
a7((7)) --> a4((4))
a7 --> a12((12))
end
subgraph notavl["非 AVL 树: 节点 7 的左右子树高度差为 2"]
n7((7)) --> n2["以 2 为根的子树, 高度 3"]
n7 --> n8["以 8 为根的子树, 高度 1"]
end动画效果可参考 Data Structure Visualizations 中的 AVL Tree。
无论是查找、插入还是删除，AVL 树在平均和最坏情况下都是 O(logn)，这比普通 BST 的最坏 O(n) 有本质提升，代价是插入和删除后可能需要旋转调整：
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
| 查找 | O(logn) | O(logn) |
| 插入 | O(logn) | O(logn) |
| 删除 | O(logn) | O(logn) |
AVL 树的实现
节点定义
AVLTree 是 AVL 树对应的类，而 AVLTreeNode 是 AVL 树节点，它是 AVLTree 的内部类。AVLTree 包含了 AVL 树的根节点，AVL 树的基本操作也定义在 AVL 树中。AVLTreeNode 包括的几个组成对象：
- key——是关键字，是用来对 AVL 树的节点进行排序的；
- left——是左孩子；
- right——是右孩子；
- height——是高度。
public class AVLTree<T extends Comparable<T>> {
private AVLTreeNode<T> mRoot; // 根结点
// AVL树的节点(内部类)
class AVLTreeNode<T extends Comparable<T>> {
T key; // 关键字(键值)
int height; // 高度
AVLTreeNode<T> left; // 左孩子
AVLTreeNode<T> right; // 右孩子
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
......
}关于高度，有的地方将”空二叉树的高度是 -1”，而本文采用维基百科上的定义：树的高度为最大层次。即空的二叉树的高度是 0，非空树的高度等于它的最大层次（根的层次为 1，根的子节点为第 2 层，依次类推）。
树的高度与比较
/*
* 获取树的高度
*/
private int height(AVLTreeNode<T> tree) {
if (tree != null)
return tree.height;
return 0;
}
public int height() {
return height(mRoot);
}
/*
* 比较两个值的大小
*/
private int max(int a, int b) {
return a>b ? a : b;
}旋转
如果在 AVL 树中进行插入或删除节点后，可能导致 AVL 树失去平衡。这种失去平衡可以概括为 4 种姿态：LL（左左）、LR（左右）、RR（右右）和 RL（右左）。
总的来说，AVL 树失去平衡时的情况一定是 LL、LR、RL、RR 这 4 种之一，它们各有各自的定义（原文配有 4 种失衡姿态的示意图，已丢失，据文字描述）：
- (1) LL: LeftLeft，也称为”左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大 2，导致 AVL 树失去了平衡。例如，根节点 (8) 的左子树 (4) 的左子树 (2) 还有非空子节点，而根节点 (8) 的右子树 (12) 没有子节点，导致”根节点 (8) 的左子树 (4) 高度”比”根节点 (8) 的右子树 (12)“高 2。
- (2) LR: LeftRight，也称为”左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大 2，导致 AVL 树失去了平衡。例如，根节点 (8) 的左子树 (4) 的右子树 (6) 还有非空子节点，而根节点 (8) 的右子树 (12) 没有子节点，导致失衡。
- (3) RL: RightLeft，称为”右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大 2，导致 AVL 树失去了平衡。例如，根节点 (8) 的右子树 (12) 的左子树 (10) 还有非空子节点，而根节点 (8) 的左子树 (4) 没有子节点，导致失衡。
- (4) RR: RightRight，称为”右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大 2，导致 AVL 树失去了平衡。例如，根节点 (8) 的右子树 (12) 的右子树 (14) 还有非空子节点，而根节点 (8) 的左子树 (4) 没有子节点，导致失衡。
AVL 失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍这 4 种情况对应的旋转方法。
LL 的旋转。LL 失去平衡的情况，可以通过一次旋转让 AVL 树恢复平衡。对于 LL 旋转，你可以这样理解为：LL 旋转是围绕”失去平衡的 AVL 根节点”进行的，也就是节点 k2；而且由于是 LL 情况，即左左情况，就用手抓着”左孩子，即 k1”使劲摇。将 k1 变成根节点，k2 变成 k1 的右子树，“k1 的右子树”变成”k2 的左子树”（原文图片丢失，据文字与代码重绘）：
flowchart TD
subgraph before["旋转前"]
k2a(("k2")) --> k1a(("k1"))
k2a --> za["Z"]
k1a --> xa["X"]
k1a --> ya["Y"]
end
subgraph after["LL 旋转后（一次右旋）"]
k1b(("k1")) --> xb["X"]
k1b --> k2b(("k2"))
k2b --> yb["Y"]
k2b --> zb["Z"]
end/*
* LL: 左左对应的情况(左单旋转)。
*
* 返回值: 旋转后的根节点
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
AVLTreeNode<T> k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height(k2.left), height(k2.right)) + 1;
k1.height = max( height(k1.left), k2.height) + 1;
return k1;
}RR 的旋转。理解了 LL 之后，RR 就相当容易理解了。RR 是与 LL 对称的情况，恢复平衡也只需要一次旋转（左旋），旋转图与 LL 对称，不再重绘：
/*
* RR: 右右对应的情况(右单旋转)。
*
* 返回值: 旋转后的根节点
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
AVLTreeNode<T> k2;
k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height(k1.left), height(k1.right)) + 1;
k2.height = max( height(k2.right), k1.height) + 1;
return k2;
}LR 的旋转。LR 失去平衡的情况，需要经过两次旋转才能让 AVL 树恢复平衡。第一次旋转是围绕”k1”进行的”RR 旋转”，第二次是围绕”k3”进行的”LL 旋转”：
/*
* LR: 左右对应的情况(左双旋转)。
*
* 返回值: 旋转后的根节点
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
k3.left = rightRightRotation(k3.left);
return leftLeftRotation(k3);
}RL 的旋转。RL 是与 LR 的对称情况。第一次旋转是围绕”k3”进行的”LL 旋转”，第二次是围绕”k1”进行的”RR 旋转”：
/*
* RL: 右左对应的情况(右双旋转)。
*
* 返回值: 旋转后的根节点
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
k1.right = leftLeftRotation(k1.right);
return rightRightRotation(k1);
}插入
插入节点：递归地按 BST 规则插入，回溯时更新高度，若某节点失衡则根据插入位置选择 LL/LR/RR/RL 旋转：
/*
* 将结点插入到AVL树中，并返回根节点
*
* 参数说明:
* tree AVL树的根结点
* key 插入的结点的键值
* 返回值:
* 根节点
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
if (tree == null) {
// 新建节点
tree = new AVLTreeNode<T>(key, null, null);
if (tree==null) {
System.out.println("ERROR: create avltree node failed!");
return null;
}
} else {
int cmp = key.compareTo(tree.key);
if (cmp < 0) { // 应该将key插入到"tree的左子树"的情况
tree.left = insert(tree.left, key);
// 插入节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.left) - height(tree.right) == 2) {
if (key.compareTo(tree.left.key) < 0)
tree = leftLeftRotation(tree);
else
tree = leftRightRotation(tree);
}
} else if (cmp > 0) { // 应该将key插入到"tree的右子树"的情况
tree.right = insert(tree.right, key);
// 插入节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.right) - height(tree.left) == 2) {
if (key.compareTo(tree.right.key) > 0)
tree = rightRightRotation(tree);
else
tree = rightLeftRotation(tree);
}
} else { // cmp==0
System.out.println("添加失败: 不允许添加相同的节点！");
}
}
tree.height = max( height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key) {
mRoot = insert(mRoot, key);
}删除
删除结点 z：与 BST 删除类似，区别在于删除左右子树都非空的节点时，选择从较高的子树中取替身（最大/最小节点），保证删除后仍然平衡；回溯过程中发现失衡则旋转修复：
/*
* 删除结点(z)，返回根节点
*
* 参数说明:
* tree AVL树的根结点
* z 待删除的结点
* 返回值:
* 根节点
*/
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
// 根为空 或者 没有要删除的节点，直接返回null。
if (tree==null || z==null)
return null;
int cmp = z.key.compareTo(tree.key);
if (cmp < 0) { // 待删除的节点在"tree的左子树"中
tree.left = remove(tree.left, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.right) - height(tree.left) == 2) {
AVLTreeNode<T> r = tree.right;
if (height(r.left) > height(r.right))
tree = rightLeftRotation(tree);
else
tree = rightRightRotation(tree);
}
} else if (cmp > 0) { // 待删除的节点在"tree的右子树"中
tree.right = remove(tree.right, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.left) - height(tree.right) == 2) {
AVLTreeNode<T> l = tree.left;
if (height(l.right) > height(l.left))
tree = leftRightRotation(tree);
else
tree = leftLeftRotation(tree);
}
} else { // tree是对应要删除的节点。
// tree的左右孩子都非空
if ((tree.left!=null) && (tree.right!=null)) {
if (height(tree.left) > height(tree.right)) {
// 如果tree的左子树比右子树高；
// 则(01)找出tree的左子树中的最大节点
// (02)将该最大节点的值赋值给tree。
// (03)删除该最大节点。
// 这类似于用"tree的左子树中最大节点"做"tree"的替身；
// 采用这种方式的好处是: 删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
AVLTreeNode<T> max = maximum(tree.left);
tree.key = max.key;
tree.left = remove(tree.left, max);
} else {
// 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
// 则(01)找出tree的右子树中的最小节点
// (02)将该最小节点的值赋值给tree。
// (03)删除该最小节点。
// 这类似于用"tree的右子树中最小节点"做"tree"的替身；
// 采用这种方式的好处是: 删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
AVLTreeNode<T> min = minimum(tree.right);
tree.key = min.key;
tree.right = remove(tree.right, min);
}
} else {
AVLTreeNode<T> tmp = tree;
tree = (tree.left!=null) ? tree.left : tree.right;
tmp = null;
}
}
return tree;
}
public void remove(T key) {
AVLTreeNode<T> z;
if ((z = search(mRoot, key)) != null)
mRoot = remove(mRoot, z);
}其余的遍历（preOrder/inOrder/postOrder）、查找（search/iterativeSearch）、最大最小值（maximum/minimum）、销毁（destroy）和打印（print）等方法与 BST 的实现完全一致，此处不再重复列出，完整实现即将上述旋转与本文代码组装即可。
AVL 树测试
- 新建 AVL 树；
- 依次添加
3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9到 AVL 树中：- 2.01 添加 3、2：不会破坏 AVL 树的平衡性；
- 2.02 添加 1：AVL 树失去平衡（LL），需要进行 LL 旋转；
- 2.03 添加 4：不会破坏平衡性；
- 2.04 添加 5：失去平衡（RR），进行 RR 旋转；
- 2.05 添加 6：失去平衡（RR），进行 RR 旋转；
- 2.06 添加 7：失去平衡（RR），进行 RR 旋转；
- 2.07 添加 16：不会破坏平衡性；
- 2.08 添加 15：失去平衡（RR），进行 RR 旋转；
- 2.09 添加 14：失去平衡（RL），进行 RL 旋转；
- 2.10 添加 13：失去平衡（RR），进行 RR 旋转；
- 2.11 添加 12：失去平衡（LL），进行 LL 旋转；
- 2.12 添加 11：失去平衡（LL），进行 LL 旋转；
- 2.13 添加 10：失去平衡（LL），进行 LL 旋转；
- 2.14 添加 8：不会破坏平衡性；
- 2.15 添加 9：失去平衡（LR），进行 LR 旋转。
以 2.02 添加 1 为例，LL 失衡与旋转过程如下（原文图片丢失，据测试流程重绘）：
flowchart TD
subgraph before["添加 1 后 LL 失衡"]
b3((3)) --> b2((2))
b2 --> b1((1))
b3 --> bn["null（右子树高度 0）"]
end
subgraph after["LL 旋转（右旋）后恢复平衡"]
a2((2)) --> a1((1))
a2 --> a3((3))
end- 打印树的信息，输出下面这棵树（据 print 结果重绘）：
flowchart TD
t7((7)) --> t4((4))
t7 --> t13((13))
t4 --> t2((2))
t4 --> t6((6))
t2 --> t1((1))
t2 --> t3((3))
t6 --> t5((5))
t13 --> t11((11))
t13 --> t15((15))
t11 --> t9((9))
t11 --> t12((12))
t9 --> t8((8))
t9 --> t10((10))
t15 --> t14((14))
t15 --> t16((16))- 删除节点 8：删除操作并不会造成 AVL 树的不平衡。删除节点 8 之后，再打印该 AVL 树的信息。
测试代码：
/**
* Java 语言: AVL树
*
* @author skywang
* @date 2013/11/07
*/
public class AVLTreeTest {
private static int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
public static void main(String[] args) {
int i;
AVLTree<Integer> tree = new AVLTree<Integer>();
System.out.printf("== 依次添加: ");
for(i=0; i<arr.length; i++) {
System.out.printf("%d ", arr[i]);
tree.insert(arr[i]);
}
System.out.printf("\n== 前序遍历: ");
tree.preOrder();
System.out.printf("\n== 中序遍历: ");
tree.inOrder();
System.out.printf("\n== 后序遍历: ");
tree.postOrder();
System.out.printf("\n");
System.out.printf("== 高度: %d\n", tree.height());
System.out.printf("== 最小值: %d\n", tree.minimum());
System.out.printf("== 最大值: %d\n", tree.maximum());
System.out.printf("== 树的详细信息: \n");
tree.print();
i = 8;
System.out.printf("\n== 删除根节点: %d", i);
tree.remove(i);
System.out.printf("\n== 高度: %d", tree.height());
System.out.printf("\n== 中序遍历: ");
tree.inOrder();
System.out.printf("\n== 树的详细信息: \n");
tree.print();
// 销毁二叉树
tree.destroy();
}
}测试结果：
== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
== 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
== 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
== 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
== 高度: 5
== 最小值: 1
== 最大值: 16
== 树的详细信息:
7 is root
4 is 7's left child
2 is 4's left child
1 is 2's left child
3 is 2's right child
6 is 4's right child
5 is 6's left child
13 is 7's right child
11 is 13's left child
9 is 11's left child
8 is 9's left child
10 is 9's right child
12 is 11's right child
15 is 13's right child
14 is 15's left child
16 is 15's right child
== 删除根节点: 8
== 高度: 5
== 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16
== 树的详细信息:
7 is root
4 is 7's left child
2 is 4's left child
1 is 2's left child
3 is 2's right child
6 is 4's right child
5 is 6's left child
13 is 7's right child
11 is 13's left child
9 is 11's left child
10 is 9's right child
12 is 11's right child
15 is 13's right child
14 is 15's left child
16 is 15's right child参考文章
- 本文主要来源于 @skywang12345 的 https://www.cnblogs.com/skywang12345/p/3577479.html ，在此基础上重新组织和增加了内容。
- 其它参考：https://blog.csdn.net/m0_37609579/article/details/99690222
系列导航
- 上一篇：树：二叉搜索树（BST）
- 下一篇：树：红黑树（R-B Tree）
- 相关篇：红黑树（BST → AVL → 红黑树的演进：AVL 严格平衡但旋转成本高，红黑树近似平衡、旋转更少）、TreeMap 源码解析