Java实现的完整AVL树：包含比较器与四种旋转操作

"本文将详细介绍AVL树的完整实现，包括插入、删除、查找等基本操作，以及如何处理不平衡情况下的四种旋转操作。此外，还会提及一个简单的异常类UnderflowException，用于处理集合为空时的操作异常。" AVL树是一种自平衡的二叉查找树，由Adelson-Velsky和Landis于1962年提出，因此得名。它的主要特点是每个节点的左右子树高度差不超过1，确保了搜索、插入和删除操作的时间复杂度稳定在O(log2N)。为了保持这种平衡状态，AVL树在插入或删除节点后可能会进行四种旋转操作：左旋、右旋、左-右旋和右-左旋。 1. **左旋** (Single Left Rotation): 当插入或删除导致某个节点的右子节点成为不平衡的高子树，且右子节点的左子节点是矮子树时，需要进行左旋。左旋操作将右子节点提升到父节点的位置，原父节点成为右子节点的新左子节点。 2. **右旋** (Single Right Rotation): 类似地，当左子节点成为不平衡的高子树，且左子节点的右子节点是矮子树时，执行右旋。右旋操作将左子节点提升至父节点位置，原父节点成为左子节点的新右子节点。 3. **左-右旋** (Double Left Rotation): 当插入或删除导致节点的右子节点较高，且右子节点的左子节点也是一个高子树时，先对右子节点执行左旋，再对原节点执行右旋。 4. **右-左旋** (Double Right Rotation): 若左子节点较高，且左子节点的右子节点为高子树，先对左子节点执行右旋，再对原节点执行左旋。 在Java中，AVL树的实现通常会包含以下方法： - `insert(x)`: 插入节点x，插入过程中检查并执行必要的旋转操作以恢复平衡。 - `remove(x)`: 删除节点x，需要考虑多种情况，如节点无子节点、有一个子节点和两个子节点，同时要维护平衡。 - `contains(x)`: 检查树中是否包含节点x，返回布尔值。 - `findMin()`: 返回树中最小的元素。 - `findMax()`: 返回树中最大的元素。 - `isEmpty()`: 检查树是否为空，返回布尔值。 - `makeEmpty()`: 清空树中的所有元素。 - `printTree()`: 打印树的所有元素，按排序顺序。 异常类`UnderflowException`是一个自定义异常，用于表示尝试在空容器上执行操作时的错误。例如，在空AVL树上尝试删除或查找元素时，可以抛出这个异常。 ```java public class AvlTree<T extends Comparable<T>> { // AVL树的节点结构 private class Node { T data; int height; Node left, right; // 构造函数 Node(T item) { data = item; height = 1; } } // 其他方法如insert、remove、contains、findMin、findMax、isEmpty、makeEmpty、printTree等在这里实现，会涉及到节点的插入、删除、查找及平衡调整等操作。 } ``` 理解AVL树的关键在于掌握四种旋转操作的逻辑，并能够判断何时需要进行旋转。对于初学者，通过编写和测试这些操作来加深理解是非常有益的。随着技能的提高，可以进一步优化和扩展AVL树的实现，比如添加自定义比较器，支持更复杂的操作，或者提高旋转操作的效率。