数据结构（Java语言）——AVLTree简单实现

    AVL(Adelson-Velskii and Landis)树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且它保证树的深度须是o(logN)。最简单的想法是要求左右子树具有相同的高度，这种想法并不要求树的深度要浅。

    另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。通常空子树的高度定义为-1，只有具有(2^k)-1个节点的理想平衡树满足这个条件。因此，虽然这种平衡条件保证了树的深度小，但是它太严格而难以使用，需要放宽条件。

    一棵AVL树是 其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树高度为-1）。可以证明，初略地说，一个AVL树的高度最多为1.44log(N+2)-1.328，但是实际上的高度只略大于logN。因此，除去可能的插入外，所有的树操作都可以以时间O(logN)。当进行插入操作时，我们需要更新通向根节点路径上的那些节点的所有平衡信息，而插入操作隐含困难的原因在于，插入一个节点可能破坏AVL树的特性。如果发生这种情况，那么就要在考虑这一步插入完成之前回复平衡的性质。事实上，这总可以通过对数惊醒简单的修正来做到，我们称其为旋转。

    在插入之后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行并更新平衡信息时，可以发现一个节点，它的新平衡破坏了AVL条件。我们将指出如何在第一个这样的节点（最深的节点）重新平衡这棵树，并证明这一重新平衡满足AVL性质。

    我们把重新平衡的节点叫做a。由于任意节点最多有两个儿子，因此出现高度不平衡就需要a点的两棵子树的高度差2。容易看出，这种平衡可能出现在下面四种情况中：

1. 对a的左儿子的左子树进行一次插入
2. 对a的左儿子的右子树进行一次插入
3. 对a的右儿子的左子树进行一次插入
4. 对a的右儿子的右子树进行一次插入

    情形1和4是关于a点的镜像对称，而2和3是关于a点的镜像对称，因此理论上只有两种情况。第一种情况是插入发生在“外边”的情况（即左-左或右-右的情况），该情况通过---对树的一次单旋转而完成调整。第二种情况是插入发生在“内部”的情况（即左-右或右-左的情况）该情况通过稍微复杂些的双旋转来处理。

• 单旋转

    下图显示了单旋转如何调整情况1。旋转前的图在左边，旋转后的图在右边。旋转前节点k2不满足AVL平衡性质，因为它的左子树比右子树深2层（图中虚线标识树的各层）。该图所描述的情况只是情形1可能的一种情况，在插入之前k2满足AVL性质，但是插入之后该性质被破坏。子树X已经长出一层，这使得他比子树Z深出2层。Y不可能与新X在同一水平上，因为那样k2在插入以前就已经失去平衡了；Y也不可能与Z在同一层上，因为那样k1就会是在通向根的路径上破坏AVL平衡条件的第一个节点。
    为使树恢复平衡，我们把X上移一层，并把Z下移一层。注意，此时实际上超出了AVL树性质的要求。为此，我们重新安排节点以形成一棵等价的树，如上右图所示。抽象形容就是，把树看成是灵活的，抓住节点k1，拉动它成为新的根。二叉查找树的性质告诉我们，在原树中k2>k1，于是在新树中k2变成了k1的右儿子，X和Z仍然分别是k1的左儿子和k2的右儿子。子树Y包含原树中介于k1和k2之间的那些节点，可以将它放在新树中k2的左儿子的位置上，这样，所有对顺序的要求得到满足。     这样的操作只需要一部分的链改变，结果我们得到另外一棵二叉查找树，它是一颗AVL树，因为X向上移动了一层，Y停在原来的水平上，而Z下移一层。k2和k1不仅满足AVL要求，而且它们的子树都恰好在同一高度上。因此，通向根节点的路径的高度不需要进一步的修正，因而也不需要进一步的旋转。情况4与情况1相对称因此也可以解决。

• 双旋转

    上面描述的算法有一个问题：如下图，对于情况2和3上面的做法无效。问题在于子树Y太深，单旋转没有降低它的深度。

    解决这个问题要用双旋转，如下：


    在上图中的子树Y已经有一项插入其中，这保证它是非空的。因此，我们可以假设它有一个根和两棵子树。于是，我们可以把整棵树看成是4棵子树由3个节点连接。如图所示，恰好树B或树C中有一棵比D深两层（除非它们都是空的），但是我们不能肯定是哪一棵。事实上这并不影响，因为在上图中B和C都被画成比D低1.5层。
    为了重新平衡，我们不能再把k3用作根了，在k3和k1之间的单旋转又不能解决问题，唯一的选择就是把k2用作新的根。这迫使k1是k2的左儿子，k3是它的右儿子，从而完全确定了这四棵树的最终位置。容易看出，最后得到的树满足AVL树的性质。我们也把树的高度恢复到插入以前的水平，这就保证所有的重新平衡和高度更新是完善的。与上面的情况2相对称，情况3也可以通过双旋转得到修正。     其实现代码如下（目前未包含删除方法）：

public class AvlTree<AnyType extends Comparable<? super AnyType>> {
private AvlNode<AnyType> root;

private static class AvlNode<AnyType> {
AnyType element;
AvlNode<AnyType> left;
AvlNode<AnyType> right;
int height;

AvlNode(AnyType theElement) {
this(theElement, null, null);
}

AvlNode(AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt) {
element = theElement;
left = lt;
right = rt;
height = 0;
}
}

private int height(AvlNode<AnyType> node) {
return node == null ? -1 : node.height;
}

public AvlTree() {
makeEmpty();
}

/**
 * 使树为空树
 */
public void makeEmpty() {
root = null;
}

/**
 * 该树是否为空树
 * 
 * @return 是否空
 */
public boolean isEmpty() {
return root == null;
}

/**
 * 该树是否存在含有参数值的节点
 * 
 * @param value
 *            元素值
 * @return 是否含该元素
 */
public boolean contains(AnyType value) {
return contains(value, root);
}

/**
 * 某个节点及它的子节点是否存在含有参数值的节点
 * 
 * @param value
 *            元素值
 * @param node
 *            节点
 * @return
 */
private boolean contains(AnyType value, AvlNode<AnyType> node) {
if (node == null) {
return false;
}
int compareResult = value.compareTo(node.element);
if (compareResult < 0) { // 插入节点值小于节点值，则递归查找左子树下
return contains(value, node.left);
} else if (compareResult > 0) { // 插入节点值大于节点值，则递归查找右子树下
return contains(value, node.right);
} else {
return true;
}
}

/**
 * 查找该树最小元素值
 * 
 * @return 最小元素值
 */
public AnyType findMin() {
if (isEmpty()) {
throw new NullPointerException();
}
return findMin(root).element;
}

/**
 * 查找某节点及其子树中的最小元素
 * 
 * @param node
 *            父节点
 * @return 最小元素所在节点
 */
private AvlNode<AnyType> findMin(AvlNode<AnyType> node) {
if (node == null) {
return null;
} else if (node.left == null) {
return node;
}
return findMin(node.left);
}

/**
 * 查找该树最大元素值
 * 
 * @return 最大元素值
 */
public AnyType findMax() {
if (isEmpty()) {
throw new NullPointerException();
}
return findMavalue(root).element;
}

/**
 * 查找某节点及其子树中的最大元素
 * 
 * @param node
 *            父节点
 * @return 最大元素
 */
private AvlNode<AnyType> findMavalue(AvlNode<AnyType> node) {
if (node == null) {
return null;
} else if (node.right == null) {
return node;
}
return findMavalue(node.right);
}

public void insert(AnyType value) {
root = insert(value, root);
}

private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> node) {
if (node == null) {
return new AvlNode<AnyType>(x);
}
int compareResult = x.compareTo(node.element);
if (compareResult < 0) {
node.left = insert(x, node.left);
if (height(node.left) - height(node.right) == 2) {
if (x.compareTo(node.left.element) < 0) {
node = rotateWithLeftChild(node);
} else {
node = doubleWithLeftChild(node);
}
}
} else if (compareResult > 0) {
node.right = insert(x, node.right);
if (height(node.right) - height(node.left) == 2) {
if (x.compareTo(node.right.element) > 0) {
node = rotateWithRightChild(node);
} else {
node = doubleWithRightChild(node);
}
}
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
return node;
}

private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2) {
AvlNode<AnyType> 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;
}

private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}

private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2) {
AvlNode<AnyType> k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.right), height(k2.left)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
return k1;
}

private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3) {
k3.right = rotateWithLeftChild(k3.right);
return rotateWithRightChild(k3);

}

/**
 * 遍历输出树
 */
public void printTree() {
if (isEmpty()) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}

/**
 * 先序遍历输出某节点下元素
 * 
 * @param node
 *            节点
 */
private void printTree(AvlNode<AnyType> node) {
if (node != null) {
printTree(node.left);
System.out.print(node.element + " ");
printTree(node.right);
}
}

public static void main(String[] args) {
AvlTree<Integer> tree = new AvlTree<Integer>();
tree.insert(10);
tree.insert(5);
tree.insert(9);
tree.insert(4);
tree.insert(8);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(6);
tree.insert(1);
tree.printTree();
}
}

执行结果： 1 2 3 4 5 6 7 8 9 10