AVL树的完整实现（含比较器，Java语言描述）
前情提要
作者：进阶的JFarmer
之前只写了一些AVL树核心算法，这里给出一个AVL树的完整实现。
AVL树是平衡查找二叉树，不仅能避免二叉搜索树出现斜树的状况，更是能保持比较标准的O(log2N)，但AVL树可能需要很多次的各种调整：
左儿子单旋转 左儿子双旋转 右儿子单旋转 右儿子双旋转最终使得AVL树维持平衡，保持较高查找效率。
调整在插入删除每一次的不平衡后进行，可能简单也可能复杂，但基本的四种“动作”是固定的。
AVL树作为数据结构，说简单也简单，说复杂也复杂。对初学者来说，一定要掌握的是检测和调整AVL树平衡（含四种旋转）的代码，随着学习的深入，应该尝试编写AVL树的完整代码。
这里就给大家提供一份可用的完整代码。
功能介绍 void insert(x) → Insert x void remove(x) → Remove x (unimplemented) boolean contains(x) → Return true if x is present boolean remove(x) → Return true if x was present Comparable findMin() → Return smallest item Comparable findMax() → Return largest item boolean isEmpty() → Return true if empty; else false void makeEmpty() → Remove all items void printTree() → Print tree in sorted order 异常类当集合容器为空的时候就不能够删除或获取元素，这时就会出现一种异常，命名为UnderflowException：
/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
*/
public class UnderflowException extends RuntimeException {}
编程实现
/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
*/
public class AvlTree<T extends Comparable> {
/**
* The tree root.
*/
private AvlNode root;
/**
* Construct the tree.
*/
public AvlTree() {
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert(T x) {
root = insert(x, root);
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove(T x) {
root = remove(x, root);
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode remove(T x, AvlNode t) {
if(t == null) {
return null; // Item not found; do nothing
}
int compareResult = x.compareTo(t.element);
if(compareResult 0) {
t.right = remove(x, t.right);
} else if(t.left != null && t.right != null) { // Two children
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
}
else
t = (t.left != null) ? t.left : t.right;
return balance(t);
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public T findMin() {
if(isEmpty()) {
throw new UnderflowException();
}
return findMin(root).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public T findMax() {
if(isEmpty()) {
throw new UnderflowException();
}
return findMax(root).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if x is found.
*/
public boolean contains(T x) {
return contains(x, root);
}
/**
* Make the tree logically empty.
*/
public void makeEmpty() {
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty() {
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree() {
if(isEmpty()) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}
private static final int ALLOWED_IMBALANCE = 1;
// Assume t is either balanced or within one of being balanced
private AvlNode balance(AvlNode 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 = rotateWithLeftChild(t);
} else {
t = doubleWithLeftChild(t);
}
} else if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE) {
if( height(t.right.right) >= height(t.right.left)) {
t = rotateWithRightChild(t);
} else {
t = doubleWithRightChild(t);
}
}
t.height = Math.max(height(t.left), height(t.right)) + 1;
return t;
}
public void checkBalance() {
checkBalance(root);
}
private int checkBalance(AvlNode t) {
if(t == null) {
return -1;
}
if(t != null) {
int hl = checkBalance(t.left);
int hr = checkBalance(t.right);
if(Math.abs(height(t.left) - height(t.right)) > 1 || height(t.left) != hl || height(t.right) != hr) {
System.out.println("OOPS!!");
}
}
return height(t);
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode insert(T x, AvlNode t) {
if(t == null) {
return new AvlNode(x, null, null);
}
int compareResult = x.compareTo(t.element);
if(compareResult 0) {
t.right = insert(x, t.right);
}
return balance(t);
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private AvlNode findMin(AvlNode t) {
if(t == null) {
return null;
}
while(t.left != null) {
t = t.left;
}
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private AvlNode findMax(AvlNode t) {
if(t == null) {
return null;
}
while(t.right != null) {
t = t.right;
}
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return true if x is found in subtree.
*/
private boolean contains(T x, AvlNode t) {
while(t != null) {
int compareResult = x.compareTo(t.element);
if(compareResult 0) {
t = t.right;
} else {
return true; // Match
}
}
return false; // No match
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree(AvlNode t) {
if(t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
/**
* Return the height of node t, or -1, if null.
*/
private int height(AvlNode t) {
return t == null ? -1 : t.height;
}
/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private AvlNode rotateWithLeftChild(AvlNode k2) {
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1;
}
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private AvlNode rotateWithRightChild(AvlNode k1) {
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k2.right), k1.height) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.
*/
private AvlNode doubleWithLeftChild(AvlNode k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then return new root.
*/
private AvlNode doubleWithRightChild(AvlNode k1) {
k1.right = rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}
private static class AvlNode {
AvlNode(T theElement) {
this(theElement, null, null);
}
AvlNode(T theElement, AvlNode lt, AvlNode rt) {
element = theElement;
left = lt;
right = rt;
height = 0;
}
T element; // The data in the node
AvlNode left; // Left child
AvlNode right; // Right child
int height; // Height
}
}
测试
public class AVLTreeTest {
public static void main(String [] args) {
AvlTree t = new AvlTree();
final int SMALL = 40;
final int NUMS = 1000000; // must be even
final int GAP = 37;
System.out.println("Checking... (no more output means success)");
for(int i = GAP; i != 0; i = ( i + GAP ) % NUMS) {
// System.out.println( "INSERT: " + i );
t.insert(i);
if(NUMS < SMALL) {
t.checkBalance();
}
}
for(int i = 1; i < NUMS; i+= 2) {
// System.out.println( "REMOVE: " + i );
t.remove(i);
if(NUMS < SMALL) {
t.checkBalance();
}
}
if(NUMS < SMALL) {
t.printTree();
}
if(t.findMin() != 2 || t.findMax() != NUMS - 2) {
System.out.println("FindMin or FindMax error!");
}
for(int i = 2; i < NUMS; i+=2) {
if(!t.contains(i)) {
System.out.println("Find error1!");
}
}
for(int i = 1; i < NUMS; i+=2) {
if(t.contains(i)) {
System.out.println("Find error2!");
}
}
}
}
测试结果：
Checking... (no more output means success)
作者：进阶的JFarmer
