AVL树

AVL树 (树ADT连载 4/13)

• 可在作者的 github仓库 中获取本文和其他文章的 markdown 源文件及相关代码。

• 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。

• 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。

🌲🌲🌲 一起手写一棵完整的 AVL 树。

❗️ 【NEW】 ❗️

• 9-15: 红黑树从入门到看开

这是小白 yuki 推出的「树ADT」系列文章的第 4 篇 (4/13) 。

---

$keywords$ :

AVL树 / 单旋转与双旋转 / 绝对平衡

本文介绍一种最早提出的自平衡二叉查找树 –– AVL树。本文重点在于展现如何设计一个AVL树类，分析主要方法的代码实现，并给出该类的完整实现代码。期待读者学习之后 能够自己写出一个方法较为完备的AVL树类 。

---

yuki的其他文章如下，欢迎阅读指正！

如下所有文章同时也在我的 github 仓库 中维护。

文章	[发布时间] 字数/览/藏/赞 (~2022-10-20)
十大排序从入门到入赘 🔥🔥🔥	[20220516] 2.5万字/64.8k览/3.7k藏/937赞
二分查找从入门到入睡 🔥🔥🔥	[20220509] 2.3万字/38.4k览/2.1k藏/503赞
并查集从入门到出门 🔥🔥	[20220514] 1.2万字/17.9k览/1.0k藏/321赞
图论算法从入门到放下 🔥🔥	[20220617] 5.6万字/19.9k览/1.3k藏/365赞
树ADT系列 (预计13篇)	系列文章，连载中
3. 二叉查找树	[20220801] 5千字
4. AVL树	[20220817] 5千字
5. splay树	[20220817] 5千字
6. 红黑树从入门到看开 🔥🤯🤯🤯	[20220915] 3万字/5.3k览/269藏/72赞
10. 树状数组从入门到下车 🔥🤯	[20220722] 1.4万字/5.8k览/196藏/72赞
11. 线段树从入门到急停 🔥🤯	[20220726] 2.5万字/8.7k览/481藏/138赞
图论相关证明系列	系列文章
1. Dijkstra正确性证明 🤯	[20220531]
2. Prim正确性证明 🤯	[20220919]
3. Bellman-Ford及SPFA正确性证明	[20220602]
4. Floyd正确性证明	[20220602]
5. 最大流最小割定理证明 🤯🤯	[20220719]
6. Edmonds-Karp复杂度证明 🤯🤯	[20220515]
7. Dinic复杂度证明 🤯🤯	[20220531]

---

[2022-10-17]

• 旋转后结点高度更新代码有误，Math.max() 取得左右子树中较高者的高度后还要加 1。感谢匿名用户提醒！🙏

---

[TOC]

---

AVL树

对于二叉查找树的插入、删除、查找等操作，时间复杂度为 $O(logn)$ 的前提是 保持树的平衡 ，即保持树的高度为 $logn$ 。在 二叉查找树 一文的删除结点的操作中，我们总是 删除目标结点右子树中的最小结点 ，可以预见多次删除操作后将使树呈现 左高右低的倾向 。而一旦树不平衡，插入、删除、查找等操作将无法达到 $O(logn)$ 的复杂度，于是我们自然会想如何在多次删除操作后，树总能够保持平衡。若一棵 BST 在操作后总能保持平衡，我们称其为 平衡 BST 。 AVL 树是最早提出的自平衡二叉查找树 。

AVL 树以 「旋转 (rotation)」 操作保证 任意结点的左右子树高度差不超过 1，使得树的深度总保持为 $O(logn)$ 。下图左侧的树是 AVL 树，右侧的树则不是 AVL 树，在结点 7 处失衡。

AVL (Adelson-Velsky and Landis Tree) 树由 G.M. Adelson-Velsky 和E.M. Landis于1962年的 论文 中首次介绍。

文本内容为 Mark Allen Weiss 所著 数据结构与算法分析：Java语言描述 相关章节的整理和总结。代码亦来自该书，略作改动。

旋转

在上图 AVL 树中插入 6 时， 6 将作为 7 的左子结点被插入，这将破坏结点 8 的平衡 (8的左子树与其右子树高差为 2)。AVL 树通过旋转操作能够恢复失衡结点的平衡，本节详细讲解此操作的细节。

考虑插入一个结点 $x$ 后，平衡被破坏的结点 $y1, y2,…$ ，这些结点只可能在 $x$ 到根结点路径上，因此 只需沿着此路径恢复平衡即可 。更进一步地，不难证明，只需在第一个平衡被破坏的结点 $y$ （ $x$ 到根结点方向）上重新平衡这棵树，即能保证整棵树恢复为 AVL 树。

插入情况必为如下四情形种之一：

情形1(左-左): 插入点在 y 的左儿子的左子树
情形2(左-右): 插入点在 y 的左儿子的右子树
情形3(右-左): 插入点在 y 的右儿子的左子树
情形4(右-右): 插入点在 y 的右儿子的右子树

其中 1 和 4，2 和 3 关于 $y$ 镜像对称，所以实际只有两种情况，但从编程角度来看需要分别处理这四种情形。对于发生在外侧的情况 (左-左，右-右) ，需要通过 单旋转 恢复平衡，对于发生在内侧的情况 (左-右，右-左) ，需要通过 双旋转 恢复平衡。

许多资料将本节介绍的左单旋、右单旋、左右双旋、右左双旋分别称作 zag, zig, zag-zig, zig-zag 操作。zig 和 zag 原意并无左右之分，为了避免歧义，本文不采用这种称呼，读者只需了解即可。在「伸展树」一节中还会有「一字型」的左左双旋和右右双旋，分别被称为 zag-zag 和 zig-zig ，也仅需了解即可。

单旋转

右单旋转 (情形1)： 如下，左侧的树是在 $k2$ 的左儿子 $k_1$ 的左子树中插入结点后导致 $k2$ 失去平衡 ( $k2$ 左子树比右子树深 2 层)。

上左图中 $X$ , $Y$ , $Z$ 的高度如此表现的依据： $Y$ 不可能与当前的 $X$ 在同一水平上，否则在插入前即失衡。$Y$ 也不可能与 $Z$ 在同一水平上，否则插入后先失衡的是 $k1$（在插入结点通往根路上第一个失衡）。

单旋转操作方法：

在失衡结点 $k2$ 和其左子结点 $k1$ 之间旋转。如图，核心操作为 k2.left = k1.right，k1.right = k2 ，可以形象地描述为将 $k1$ 提起，$k_2$ 下沉的同时 $Y$ 被抖落到 $k2$ 的左侧。旋转方向为右侧，即顺时针方向，且只有一次旋转操作，因此称为 右单旋转 。旋转后以 $k2$ 和 $k1$ 为根结点的树的高度也需要实时调整（ $height$ 是 $AvlNode$ 类的属性）。如下是该左-左单旋转的代码实现。

private AvlNode<E> rotateRight(AvlNode<E> k2){ // 传入失衡结点
    AvlNode<E> k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    k2.height = Math.max(height(k2.left), height(k2.right)) + 1; // 调整k2高度
    k1.height = Math.max(height(k1.left), height(k1.right)) + 1; // 调整k1高度
    return k1; // 返回调整后原失衡处结点 (已变为 k1)
}

如图调整，将 $k1$ 作为调整后树的根结点，$X$ 上移 1 层，$Y$ 深度不变，$Z$ 下移 1 层，调整后 $XYZ$ 深度相同，树高度恢复为插入前的高度。

左单旋转(情形4)： 如下，左侧的树在 $k1$ 的右儿子 $k_2$ 的右子树中插入结点后导致 $k1$ 失去平衡 ( $k1$ 右子树比左子树深 2 层)。

恢复平衡的旋转操作与左-左单旋转类似，核心操作为 k1.right = k2.left，k2.left = k1 。旋转方向为左侧，即逆时针方向，且只有一次旋转操作，因此称为 左单旋转 。以下给出右-右单旋转的代码实现。

private AvlNode<E> rotateLeft(AvlNode<E> k1){ // 传入失衡结点
    AvlNode<E> k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    // 调整平衡后更新k1，k2的高度
    k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
    k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
    return k2; // 返回调整后原失衡处结点 (已变为 k2)
}

双旋转

左右双旋转(情形2)： 如下图左侧的树，在 $k2$ 的左儿子 $k1$ 的右子树中插入结点后导致 $k2$ 失衡 ( $k2$ 的左子树比右子树高 2)。

对于情形2和情形3，单旋转无法恢复平衡。如下图，执行一次单旋转后 $k1$ 的右子树比左子树高 2，平衡未恢复。恢复此情形的平衡需采用 「双旋转」 操作。

双旋转操作方法：

将上述左-右失衡情形 (情形2) 表示为下图。导致失衡的结点插入位置为 $k1$ 的右子树，因此可以表示为 $k2$ 及其左右子树的结构。

如前述，单旋转将 $k1$ 作为根无效，因此考虑将 $k2$ 作为根，将 $k2$ 的左子树 $B$ 作为 $k1$ 的右子树，$k2$ 的右子树 $C$ 作 为$k3$ 的左子树。然后 $k2$ 的左右儿子分别更新为 $k1$ ， $k3$ 。如下图，平衡恢复。该双旋转实际上可以通过对 $k1$ 执行一次左单旋转，再对 $k3$ 执行一次右单旋转实现。可以看到代码实现十分简洁。

/**
 * 左右双旋
 * 因k2的左子结点的内侧子树，即k2的左子结点的右子树导致k2失衡。
 * 对k2执行一次右单旋转后仍然在k1处(新根)失衡，因此考虑展开一开始导致失衡的k1右子树，
 * 做如下转换(总是以中序遍历的顺序标注结点，注意k1,k2,k3位置变化)。
 * 因为不知道是B或C中的哪一棵导致失衡(比D深2层)，所以将B，C画成比D深1.5。
 * 依次执行如下两次单旋转后可恢复原失衡处的平衡。
 * 1. 对k1(k3.left)执行左单旋转。
 * 2. 对k3执行右单旋转。
 *
 *           k2                        k3
 *         /    \                    /     \
 *        k1     /\　  转换为        k1      /\
 *       /  \   /__\   ====>      /   \    /__\
 *     /\    /\   Z             /\     k2    D
 *    /__\  /  \               /__\   /  \
 *     X   /    \               A   /\    /\
 *        /______\                 /  \  /  \
 *           Y                    /____\/____\　
 *                                  B      C
 *                         k3                                k2
 *                       /     \                         /        \
 *  对k1执行             k2      /\    对k3执行           K1          K3
 *  一次左单旋转         /    \  /__\   一次右单旋转      /    \       /  \
 *    =====>         k1      /\  D    ====>          /\    /\     /\   /\
 *                 /   \    /  \                    /__\  /　\   / 　\ /__\
 *                /\    /\ /____\                    A   /____\ /____\  D
 *               /__\  /  \  C                             B      C
 *　　　　         A   /____\　
 *                      B
 */
private AvlNode<E> rotateLeftRight(AvlNode<E> k3){ // 传入失衡结点
    k3.left = rotateLeft(k3.left);
    return rotateRight(k3);
}

右-左双旋转(情形3)： 如下图左侧的树，在 $k_1$ 的右儿子 $k_3$ 的左子树中插入结点后导致 $k_1$ 失衡 ( $k_1$ 的右子树比左子树高 2)。

恢复平衡的旋转操作与左右双旋转类似，以下给出右左双旋转的代码实现。

private AvlNode<E> rotateRightLeft(AvlNode<E> k1){
    k1.right = rotateRight(k1.right);
    return rotateLeft(k1);
}

AVL树类架构

以下是AVL查找树类 AvlTree 的架构。

类成员/方法	描述
private AvlNode<E> root	字段，AVL树的根结点
private static final int ALLOWED_IMBALANCE = 1	常量字段，结点的失衡判定值，大于此值则失衡
public AvlTree()	无参构造器，$root$ 初始化为 $null$
public void makeEmpty()	树置空
public boolean isEmpty()	判断树是否为空
public void insert(E e)	插入结点驱动方法
public void remove(E e)	删除结点驱动方法
public E findMin()	查找最小结点驱动方法
public E findMax()	查找最大结点驱动方法
public boolean contains(E e)	判断是否包含指定元素驱动方法
public void printTree()	按中序遍历打印树的驱动方法
public int size()	求树的结点个数驱动方法
public int height()	求树的高度驱动方法
public void checkBalance()	树平衡检查驱动方法
private AvlNode<E> balance(AvlNode<E> t)	调整 $t$ 结点处的平衡，并返回 $t$ 。 如果 $t$ 失去平衡，根据其失衡的情况，执行如下四种情形之一的旋转调整。 左外情形，对 $t$ 执行右单旋转 $rotateRight$ 左内情形，对 $t$ 执行左右双旋转 $rotateLeftRight$ 右外情形，对 $t$ 执行左单旋转 $rotateLeft$ 右内情形，对 $t$ 执行右左双旋转 $rotateRightLeft$
private AvlNode<E> insert(E e, AvlNode<E> t)	插入结点 与 BST 的不同在于返回时调用 $balance(t)$ ， 调整插入 $t$ 后 $t$ 处的平衡，返回 $t$ 。
private AvlNode<E> remove(E e, AvlNode<E> t)	删除结点(懒惰删除) 与 BST 的不同在于返回时调用 $balance(t)$ ， 调整删除 $t$ 后 $t$ 处的平衡，返回 $t$ (新 $t$ )。
private AvlNode<E> findMin(AvlNode<E> t)	返回树的最小结点
private AvlNode<E> findMax(AvlNode<E> t)	返回树的最大结点
private boolean contains(E e, AvlNode<E> t)	判断树中是否有指定元素的结点
private void printTree(AvlNode<E> t)	中序遍历打印树
private int height(AvlNode<E> t)	返回以 $t$ 为根结点的树的高度
private int size(AvlNode<E> t)	递归地遍历所有结点，返回结点总数
private int checkBalance(AvlNode<E> t)	检查树是否平衡，不平衡打印“imbalance”，并返回树高度
private AvlNode<E> rotateRight(AvlNode<E> k2)	右单旋转
private AvlNode<E> rotateLeft(AvlNode<E> k1)	左单旋转
private AvlNode<E> rotateLeftRight(AvlNode<E> k3)	左右双旋转
private AvlNode<E> rotateRightLeft(AvlNode<E> k1)	右左双旋转

以下为 AVL 树结点嵌套类 $AvlNode$ 的架构。

类成员/方法	描述
public E element	字段，本结点元素
public AvlNode<E> left	字段，本结点的左子结点
public AvlNode<E> right	字段，本结点的右子结点
public int height	字段，该结点的高度
public AvlNode(E theElement)	构造器
public AvlNode(E element, AvlNode<E> left, AvlNode<E> right)	构造器

主要方法

insert

插入结点操作由插入驱动方法和具体插入方法完成，与 BST 的插入方法的不同在于，插入后通过 $balance$ 方法，调整 $t$ 处的平衡后通过返回原根。由于递归，$balance$ 方法能够自底向上调整 插入路径上所有结点的平衡 ，且实际上在调整 第一个（自底向上方向上的第一个）失衡结点后使整棵树恢复为 AVL 树。$balance$ 方法后续详述。

public void insert(E e) { // 插入结点驱动方法
    root = insert(e, root);
}
private AvlNode<E> insert(E e, AvlNode<E> t){ // 插入结点，返回时沿路检查平衡并调整
    if(t == null) return new AvlNode<>(e,null, null);
    int compareRes = e.compareTo(t.element);
    if(compareRes < 0) t.left = insert(e, t.left);
    else if(compareRes > 0) t.right = insert(e, t.right);
    // 等于时不插入(以该树只能存放不同的元素为前提)
    return balance(t); // 调整t处的平衡并返回t
}

findMin/findMax

与 BST 的对应方法一致。

public E findMin() { // 查找最小结点驱动方法
    if(isEmpty()) throw new NoSuchElementException();
    return findMin(root).element;
}
private AvlNode<E> findMin(AvlNode<E> t){ // 返回树的最小结点(递归方式)
    if(t == null) return null;
    else if(t.left == null) return t;
    return findMin(t.left);
}
public E findMax(){ // 查找最大结点驱动方法
    if(isEmpty()) throw new NoSuchElementException();
    return findMax(root).element;
}
private AvlNode<E> findMax(AvlNode<E> t){ // 返回树的最大结点(循环方式)
    if(t == null) return null;
    while(t.right != null) t = t.right;
    return t;
}

remove

删除结点操作由删除驱动方法和具体删除方法完成，与 BST 的删除方法的不同在于，删除后通过 $balance$ 方法，调整 $t$ 处的平衡后通过返回原根。由于递归，$balance$ 方法能够自底向上调整 插入路径上所有结点的平衡 ，且实际上在调整 第一个（自底向上方向上的第一个）失衡结点后使整棵树恢复为 AVL 树。$balance$ 方法后续详述。

public void remove(E e) { // 删除结点驱动方法
    root = remove(e, root);
}
private AvlNode<E> remove(E e, AvlNode<E> t){ // 删除结点(懒惰删除)，返回时沿路检查平衡并调整
    if(t == null) return null;
    int compareRes = e.compareTo(t.element);
    if(compareRes < 0) t.left = remove(e, t.left); // 递归地在左侧寻找
    else if(compareRes > 0) t.right = remove(e, t.right); // 递归地在右侧寻找
    // e等于t.element，分两种情形
    else if(t.left != null && t.right != null) { // 情形1：该t的左右子结点均不为null
        t.element = findMin(t.right).element; // 在右子树中找min
        t.right = remove(t.element, t.right); // 此时min已是t.element，必为情形2
    }
    else t = (t.left != null) ? t.left : t.right; // 情形2: 1以外的情形
    return balance(t); // 调整t处的平衡并返回t
}

contains

与 BST 的对应方法一致。

public boolean contains(E e) { // 判断是否包含指定元素驱动方法
    return contains(e, root);
}
private boolean contains(E e, AvlNode<E> t) {
    if(t == null) return false;
    int compareRes = e.compareTo(t.element);
    if(compareRes < 0) return contains(e, t.left);
    else if(compareRes > 0) return contains(e, t.right);
    else return true;
}

balance

在每一次插入或删除结点后，路径上结点 $t$ 的平衡。判断 $t$ 的左右子树高差是否超过设定的值（ALLOWED_IMBALANCE = 1），若超过则分别判断属于左-左、左-右、右-右、右-左中的哪一种情形，调用相应的旋转方法调整即可。该方法返回 $t$ 。

private AvlNode<E> balance(AvlNode<E> t){ // 调整 t 结点处的平衡，并返回 t
    if(t == null) return null;
    if(height(t.left) - height(t.right) > ALLOWED_IMBALANCE) { // 失衡，且左高于右
        if(height(t.left.left) >= height(t.left.right)){ // 右单旋情形
            t = rotateRight(t);
        }
        else t = rotateLeftRight(t); // 左右双旋情形
    }
    else if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE){ // 失衡，且右高于左
        if(height(t.right.right) >= height(t.right.left)) { // 左单旋情形
            t = rotateLeft(t);
        }
        else t = rotateRightLeft(t); // 右左双旋情形
    }
    t.height = Math.max(height(t.left), height(t.right)) + 1; // 更新 t 的高度
    return t;
}

rotateRight

右单旋转，见前述说明。

rotateLeft

左单旋转，见前述说明。

rotateLeftRight

左右双旋转，见前述说明。

rotateRightLeft

右左双旋转，见前述说明。

checkBalance

检查整棵树是否平衡的方法。由平衡检查驱动方法和具体平衡检查方法完成。具体方法中以递归方式检查，若平衡则返回树高，不平衡则打印 $imbalance$ 并返回树高。

public void checkBalance() { // 树平衡检查驱动方法
    checkBalance(root);
}
private int checkBalance(AvlNode<E> t) { // 检查树是否平衡，不平衡打印“imbalance”，并返回树高度
    if(t == null) return -1;
    int lh = checkBalance(t.left);
    int rh = checkBalance(t.right);
    if(Math.abs(height(t.left) - height(t.right)) > 1
            || height(t.left) != lh || height(t.right) != rh) {
        System.out.println("imbalance");
    }
    return height(t);
}

类的实现代码

class AvlTree<E extends Comparable<? super E>>{
    private AvlNode<E> root;
    private static final int ALLOWED_IMBALANCE = 1;
    public AvlTree() {} // 无参构造器
    public void makeEmpty() { // 树置空
        root = null;
    }
    public boolean isEmpty() { // 树判空
        return root == null;
    }
    public void insert(E e) { // 插入结点驱动方法
        root = insert(e, root);
    }
    public void remove(E e) { // 删除结点驱动方法
        root = remove(e, root);
    }
    public E findMin() { // 查找最小结点驱动方法
        if(isEmpty()) throw new NoSuchElementException();
        return findMin(root).element;
    }
    public E findMax(){ // 查找最大结点驱动方法
        if(isEmpty()) throw new NoSuchElementException();
        return findMax(root).element;
    }
    public boolean contains(E e) { // 判断是否包含指定元素驱动方法
        return contains(e, root);
    }
    public void printTree(){ // 按中序遍历打印树的驱动方法
        if(isEmpty()) System.out.println("Empty tree");
        else printTree(root);
    }
    public int size() { // 求树的结点个数驱动方法
        return size(root);
    }
    public int height() { // 求树的高度驱动方法
        return height(root);
    }
    public void checkBalance() { // 树平衡检查驱动方法
        checkBalance(root);
    }
    private AvlNode<E> balance(AvlNode<E> t){ // 调整 t 结点处的平衡，并返回 t
        if(t == null) return null;
        if(height(t.left) - height(t.right) > ALLOWED_IMBALANCE) { // 失衡，且左高于右
            if(height(t.left.left) >= height(t.left.right)){ // 右单旋情形
                t = rotateRight(t);
            }
            else t = rotateLeftRight(t); // 左右双旋情形
        }
        else if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE){ // 失衡，且右高于左
            if(height(t.right.right) >= height(t.right.left)) { // 左单旋情形
                t = rotateLeft(t);
            }
            else t = rotateRightLeft(t); // 右左双旋情形
        }
        t.height = Math.max(height(t.left), height(t.right)) + 1; // 更新 t 的高度
        return t;
    }
    private AvlNode<E> insert(E e, AvlNode<E> t){ // 插入结点，返回时沿路检查平衡并调整
        if(t == null) return new AvlNode<>(e,null, null);
        int compareRes = e.compareTo(t.element);
        if(compareRes < 0) t.left = insert(e, t.left);
        else if(compareRes > 0) t.right = insert(e, t.right);
        // 等于时不插入(以该树只能存放不同的元素为前提)
        return balance(t); // 调整t处的平衡并返回t
    }
    private AvlNode<E> remove(E e, AvlNode<E> t){ // 删除结点(懒惰删除)，返回时沿路检查平衡并调整
        if(t == null) return null;
        int compareRes = e.compareTo(t.element);
        if(compareRes < 0) t.left = remove(e, t.left); // 递归地在左侧寻找
        else if(compareRes > 0) t.right = remove(e, t.right); // 递归地在右侧寻找
        // e等于t.element，分两种情形
        else if(t.left != null && t.right != null) { // 情形1：该t的左右子结点均不为null
            t.element = findMin(t.right).element; // 在右子树中找min
            t.right = remove(t.element, t.right); // 此时min已是t.element，必为情形2
        }
        else t = (t.left != null) ? t.left : t.right; // 情形2: 1以外的情形
        return balance(t); // 调整t处的平衡并返回t
    }
    private AvlNode<E> findMin(AvlNode<E> t){ // 返回树的最小结点(递归方式)
        if(t == null) return null;
        else if(t.left == null) return t;
        return findMin(t.left);
    }
    private AvlNode<E> findMax(AvlNode<E> t){ // 返回树的最大结点(循环方式)
        if(t == null) return null;
        while(t.right != null) t = t.right;
        return t;
    }
    private boolean contains(E e, AvlNode<E> t) { // 判断树中是否有指定元素的结点
        if(t == null) return false;
        int compareRes = e.compareTo(t.element);
        if(compareRes < 0) return contains(e, t.left);
        else if(compareRes > 0) return contains(e, t.right);
        else return true;
    }
    private void printTree(AvlNode<E> t) { // 中序遍历打印树
        if(t != null) {
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }
    private int height(AvlNode<E> t) { // 返回以t为根结点的树的高度
        return t == null ? -1 : t.height;
    }
    private int size(AvlNode<E> t) { // 递归地遍历所有结点，返回结点总数
        if(t != null) {
            if(t.left != null && t.right != null) {
                return 1 + size(t.left) + size(t.right);
            }
            else {
                return t.left != null ? 1 + size(t.left) : 1 + size(t.right);
            }
        }
        return 0;
    }
    private int checkBalance(AvlNode<E> t) { // 检查树是否平衡，不平衡打印“imbalance”，并返回树高度
        if(t == null) return -1;
        int lh = checkBalance(t.left);
        int rh = checkBalance(t.right);
        if(Math.abs(height(t.left) - height(t.right)) > 1
                || height(t.left) != lh || height(t.right) != rh) {
            System.out.println("imbalance");
        }
        return height(t);
    }
    private AvlNode<E> rotateRight(AvlNode<E> k2){ // 右单旋
        AvlNode<E> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1; // 调整k2高度
        k1.height = Math.max(height(k1.left), height(k1.right)) + 1; // 调整k1高度
        return k1; // 返回调整后原失衡处结点
    }
    private AvlNode<E> rotateLeft(AvlNode<E> k1){ // 左单旋
        AvlNode<E> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left), height(k1.right)) + 1; // 调整k1高度
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1; // 调整k2高度
        return k2; // 返回调整后原失衡处结点
    }
    private AvlNode<E> rotateLeftRight(AvlNode<E> k3){ // 左右双旋
        k3.left = rotateLeft(k3.left);
        return rotateRight(k3);
    }
    private AvlNode<E> rotateRightLeft(AvlNode<E> k1){ // 右左双旋
        k1.right = rotateRight(k1.right);
        return rotateLeft(k1);
    }
    /**
     * AVL树结点嵌套类
     */
    private static class AvlNode<E>{
        public E element;
        public AvlNode<E> left, right;
        // 比BinaryNode多维护一个height字段，每次insert或remove一个结点时通过balance方法更新
        public int height;
        @SuppressWarnings("unused")
        public AvlNode(E theElement){
            this(theElement, null, null);
        }
        public AvlNode(E element, AvlNode<E> left, AvlNode<E> right){
            this.element = element;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }
}

测试代码

package com.yukiyama;

import java.util.NoSuchElementException;

public class AvlTreeDemo {

    public static void main(String[] args) {
        AvlTree<Integer> t = new AvlTree<>( );
        int[] elements = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
        for(int e : elements) t.insert(e);
        t.printTree();
        System.out.printf("size: %d, height: %d, min: %d, max: %d\n", t.size(), t.height(), t.findMin(), t.findMax()); // 输出10
        System.out.printf("has 10? %s, has 100? %s\n", t.contains(10), t.contains(100));
        t.checkBalance();
        t.remove(1); t.checkBalance();
        t.remove(10); t.checkBalance();
        t.remove(16); t.checkBalance();
        t.printTree(); // 8 10 13 20 29 74 98
        System.out.printf("size: %d, height: %d\n", t.size(), t.height());// 输出0
        System.out.println("is empty: " + t.isEmpty()); // false
        t.makeEmpty();
        System.out.println("is empty: " + t.isEmpty()); // true
    }

}