AVL树的是一种平衡的二叉搜索树。每次插入，删除的时候需要一个局部的平衡化操作。
实现AVL树的插入操作一般不是很难，清楚的理解了平衡因子以及旋转操作实现起来就没多大问题了。
难点一般在于删除操作的实现，教科书上一般用很大的篇幅来详细说明各种情况，看起来很凌乱，理解起来很是费劲。考虑到可以把删除操作看成插入操作的逆操作，这里我给出另一种较为清晰的实现方式：
1）删除的时候做一个标记的过程
类似于基本BST的删除定位操作，定位到要删除的节点，如果该节点左右子节点都不为空，找到该节点中序的前驱节点，交换该节点和删除节点的内容，这样下面真正删除的时候就会去删原本节点的中序前驱。
如果只是交换，那么明显破环了搜索树的性质，因为把值更大的待删节点的值放到了相对小的值的左子树。
这里我们还要标记那个交换上去的节点，使得真正搜索的时候能够沿着正确的路径到交换出去的待删除节点。
2）执行真正的删除操作
这时候，它的操作基本上跟插入操作完全对应了，因为把待删除节点放到了叶节点（或者有空子树）的位置
从而避免了别的繁琐的判断。
另外，插入的时候除了关键码重复的情况总是能保证把节点插入正确的位置，而删除的时候由于标记过程的存在，在真正删除的过程我们也总是能保证在可能需要调整平衡因子的最底端找到待删节点。然后沿着来的路径逐步平衡上去，从而保证了算法的正确性。
先给出BST树的接口：
package algorithms.tree;
/**
* @author yovn
*
*/
public interface BSTree<E extends Comparable<E>> {
public static interface Visitor<E extends Comparable<E>>
{
void visit(E ele);
}
void insert(E ele);
boolean search(E ele);
boolean isEmpty();
boolean delete(E ele);
void preOrder(Visitor<E> v);
void inOrder(Visitor<E> v);
void postOrder(Visitor<E> v);
void levelOrder(Visitor<E> v);
}
下面是基本二叉搜索树的实现：
package algorithms.tree;
import java.util.ArrayList;
import org.omg.CORBA.BooleanHolder;
/**
* @author yovn
*
*/
public class DefaultBSTree<E extends Comparable<E>> implements BSTree<E> {
protected static class BSTNode<E extends Comparable<E>> {
protected BSTNode<E> left;
protected BSTNode<E> right;
protected E key;
BSTNode(E key)
{
this.key=key;
left=right=null;
}
}
protected BSTNode<E> root;
public void insert(E ele)
{
if (root == null) {
root = new BSTNode<E>(ele);
}
else _insert(root,ele);
}
private final void _insert(BSTNode<E> pointer,E ele)
{
int cmp=pointer.key.compareTo(ele);
if(cmp==0)
{
throw new IllegalArgumentException();
}
if(cmp>0)
{
if(pointer.left==null)
{
pointer.left =new BSTNode<E>(ele);
return;
}
_insert(pointer.left,ele);
}
else
{
if(pointer.right==null)
{
pointer.right=new BSTNode<E>(ele);
return ;
}
_insert(pointer.right,ele);
}
}
public boolean search(E ele)
{
return _search(root,ele);
}
private boolean _search(BSTNode<E> pointer, E ele) {
if(pointer==null)return false;
int cmp=pointer.key.compareTo(ele);
if(cmp==0)
{
return true;
}
if(cmp>0)
{
return _search(pointer.left,ele);
}
else
{
return _search(pointer.right,ele);
}
}
public boolean delete(E ele)
{
BooleanHolder mark=new BooleanHolder(false);
root=_delete(root,ele,mark);
return mark.value;
}
private BSTNode<E> _delete(BSTNode<E> pointer, E ele,BooleanHolder mark) {
if(pointer==null)return null;
int cmp=pointer.key.compareTo(ele);
if(cmp==0)
{
mark.value=true;
if(pointer.left==null)
{
return pointer.right;
}
else if(pointer.right==null)
{
return pointer.left;
}
else
{
BSTNode<E> ret=pointer.left;//find and replace the left child's right most child or itself
BSTNode<E> retP=null;
while(ret.right!=null)
{
retP=ret;
ret=ret.right;
}
retP.right=ret.left;
ret.right=pointer.right;
ret.left=pointer.left;
return ret;
}
}
if(cmp>0)
{
pointer.left=_delete(pointer.left,ele,mark);
}
else
{
pointer.right=_delete(pointer.right,ele,mark);
}
return pointer;
}
@Override
public void inOrder(algorithms.tree.BSTree.Visitor<E> v) {
_inOrder(root,v);
}
private final void _inOrder(BSTNode<E> p, Visitor<E> v) {
if(p==null)
{
return;
}
_inOrder(p.left,v);
v.visit(p.key);
_inOrder(p.right,v);
}
@Override
public void postOrder(algorithms.tree.BSTree.Visitor<E> v) {
_postOrder(root,v);
}
private final void _postOrder(BSTNode<E> p, Visitor<E> v) {
if(p==null)
{
return;
}
_postOrder(p.left,v);
_postOrder(p.right,v);
v.visit(p.key);
}
@Override
public void preOrder(algorithms.tree.BSTree.Visitor<E> v) {
_preOrder(root,v);
}
private final void _preOrder(BSTNode<E> p, Visitor<E> v) {
if(p==null)
{
return;
}
v.visit(p.key);
_preOrder(p.left,v);
_preOrder(p.right,v);
}
@Override
public void levelOrder(algorithms.tree.BSTree.Visitor<E> v) {
if(root==null)
{
return;
}
ArrayList<BSTNode<E>> queue=new ArrayList<BSTNode<E>>();
queue.add(root);
while(!queue.isEmpty())
{
BSTNode<E> p=queue.remove(0);
v.visit(p.key);
if(p.left!=null)queue.add(p.left);
if(p.right!=null)queue.add(p.right);
}
}
@Override
public boolean isEmpty() {
return root==null;
}
}
基本二叉搜索的插入/删除操作是很基本的，AVL树的插入/删除可以看做是在此基础上多了个平衡化操作。
下面是AVL树的实现，很容易看出插入和删除的对称：
package algorithms.tree;
/**
*
* @author yovn
*
* @param <E>
*/
public class AVLTree<E extends Comparable<E>> extends DefaultBSTree<E> {
static class AVLTreeNode<E extends Comparable<E>> extends BSTNode<E> {
int bf;//balance factor
boolean marked;
AVLTreeNode(E key) {
super(key);
bf=0;
marked=false;
}
}
private static class BooleanHolder
{
BooleanHolder(boolean v)
{
value=v;
}
boolean value;
}
public void insert(E ele)
{
if (root == null) {
root = new AVLTreeNode<E>(ele);
return;
}
BooleanHolder bh=new BooleanHolder(false);
root=_insert((AVLTreeNode<E>)root,ele,bh);
}
@Override
public boolean delete(E ele) {
if (root == null) {
return false;
}
//we first marked the delete
//this will make the delete procedure be more simple as insert
if(!_mark_delete(ele))return false;
BooleanHolder heightChange=new BooleanHolder(false);
root=__real_delete((AVLTreeNode<E>)root,ele,heightChange);
//we can assume it will always be deleted
return true;
}
/**
* If we find the delete node have to child, we will exchange it value with its previous in-order sibling,
* and mark it , to help the real delete procedure know its marked and go to its left child.
* @param ele
* @return
*/
private boolean _mark_delete(E ele) {
BSTNode<E> p=root;
int cmp;
while(p!=null&&(cmp=p.key.compareTo(ele))!=0)
{
if(cmp>0)p=p.left;
else p=p.right;
}
if(p==null)
{
//not found
return false;
}
//we only take care this case
if(p.left!=null&&p.right!=null)
{
BSTNode<E> toMark=p;
p=p.left;
while(p.right!=null)
{
p=p.right;
}
//do mark now
toMark.key=p.key;
//transfer the value to p;
p.key=ele;
((AVLTreeNode<E>)toMark).marked=true;
((AVLTreeNode<E>)p).marked=false;
}
return true;
}
private BSTNode<E> __real_delete(AVLTreeNode<E> pointer, E ele, BooleanHolder heightChange) {
int cmp=ele.compareTo(pointer.key);
if(cmp==0)
{
//we really found it
//we can assume the pointer now have at most only one child.
heightChange.value=true;
if(pointer.left==null&&pointer.right==null)
{
return null;
}
else
{
return pointer.left!=null?pointer.left:pointer.right;
}
}
else if(cmp>0&&!pointer.marked)
{
pointer.marked=false;//okay, we mark it back.
pointer.right=__real_delete((AVLTreeNode<E>)pointer.right,ele,heightChange);
if(heightChange.value)
{
if(pointer.bf==-1)
{
if(((AVLTreeNode<E>)pointer.left).bf<=0)//0 or -1
{
if(((AVLTreeNode<E>)pointer.left).bf==0)
{
heightChange.value=false;//this case height will not decrease
}
pointer=LL_Rotation(pointer);
}
else
{
pointer=LR_Rotation(pointer);
}
}
else if(pointer.bf==0)
{
pointer.bf=-1;
}
else
{
pointer.bf=0;
heightChange.value=false;// the height not decrease
}
}
return pointer;
}
else
{
pointer.marked=false;//okay, we mark it back.
pointer.left=__real_delete((AVLTreeNode<E>)pointer.left,ele,heightChange);
if(heightChange.value)
{
if(pointer.bf==1)
{
if(((AVLTreeNode<E>)pointer.right).bf>=0)//0 or 1
{
if(((AVLTreeNode<E>)pointer.right).bf==0)
{
heightChange.value=false;//this case height will not decrease
}
pointer=RR_Rotation(pointer);
}
else
{
pointer=RL_Rotation(pointer);
}
}
else if(pointer.bf==0)
{
pointer.bf=1;
}
else
{
pointer.bf=0;
heightChange.value=false;// the height not decrease
}
}
return pointer;
}
}
private AVLTreeNode<E> _insert(AVLTreeNode<E> pointer, E ele, BooleanHolder heightAdded) {
int cmp=ele.compareTo(pointer.key);
if(cmp==0)
{
throw new IllegalArgumentException("duplicate key");
}
if(cmp<0)
{
if(pointer.left==null)
{
AVLTreeNode<E> node=new AVLTreeNode<E>(ele);
node.bf=0;
pointer.left=node;
if(pointer.right==null)
{
pointer.bf=-1;
heightAdded.value=true;
}
else
{
pointer.bf=0;//while no left child, the right tree can't have more than two children
heightAdded.value=false;
}
return pointer;
}
heightAdded.value=false;
pointer.left=_insert((AVLTreeNode<E>)pointer.left,ele,heightAdded);
if(heightAdded.value)
{
if(pointer.bf==-1)
{
if(((AVLTreeNode<E>)pointer.left).bf==-1)
{
//LL Rotation
pointer=LL_Rotation(pointer);
}
else if(((AVLTreeNode<E>)pointer.left).bf==1)
{
//LR Double Rotation
pointer=LR_Rotation(pointer);
}
//can't be 0
heightAdded.value=false;
}
else if(pointer.bf==1)
{
pointer.bf=0;
heightAdded.value=false;
}
else
{
pointer.bf=-1;
}
}
return pointer;
}
else
{
if(pointer.right==null)
{
AVLTreeNode<E> node=new AVLTreeNode<E>(ele);
node.bf=0;
pointer.right=node;
if(pointer.left==null)
{
pointer.bf=1;
heightAdded.value=true;
}
else
{
pointer.bf=0;//while no right child, the left tree can't have more than two children
heightAdded.value=false;
}
return pointer;
}
pointer.right=_insert((AVLTreeNode<E>)pointer.right,ele,heightAdded);
if(heightAdded.value)
{
if(pointer.bf==1)
{
if(((AVLTreeNode<E>)pointer.right).bf==1)
{
//RR Rotation
pointer=RR_Rotation(pointer);
}
else if(((AVLTreeNode<E>)pointer.right).bf==-1)
{
//RL Double Rotation
pointer=RL_Rotation(pointer);
}
//can't be 0
heightAdded.value=false;
}
else if(pointer.bf==-1)
{
pointer.bf=0;
heightAdded.value=false;
}
else
{
pointer.bf=1;
}
}
return pointer;
}
}
private AVLTreeNode<E> LR_Rotation(AVLTreeNode<E> pointer) {
AVLTreeNode<E> a, b,c;
a=pointer;
b=(AVLTreeNode<E>)pointer.left;
c=(AVLTreeNode<E>)b.right;
b.right=c.left;
c.left=b;
a.left=c.right;
c.right=a;
if(c.bf==1)
{
b.bf=-1;
c.bf=0;
a.bf=0;
}
else if(c.bf==-1)
{
a.bf=1;
b.bf=0;
c.bf=0;
}
else if(c.bf==0)// which means delete cause rotation
{
c.bf=b.bf=0;
a.bf=0;
}
return c;
}
private AVLTreeNode<E> LL_Rotation(AVLTreeNode<E> pointer) {
AVLTreeNode<E> a, b;
a=pointer;
b=(AVLTreeNode<E>)a.left;
a.left=b.right;
b.right=a;
if(b.bf==0)
{
b.bf=1;
//a's bf still be -1;
}
else if(b.bf==-1)
{
a.bf=b.bf=0;
}
return b;
}
private AVLTreeNode<E> RL_Rotation(AVLTreeNode<E> pointer) {
AVLTreeNode<E> a, b,c;
a=pointer;
b=(AVLTreeNode<E>)a.right;
c=(AVLTreeNode<E>)b.left;
b.left=c.right;
c.right=b;
a.right=c.left;
c.left=a;
if(c.bf==1)
{
a.bf=-1;
b.bf=c.bf=0;
}
else if(c.bf==-1)
{
b.bf=1;
a.bf=c.bf=0;
}
else//delete cause rotation
{
a.bf=b.bf=c.bf=0;
}
return c;
}
private AVLTreeNode<E> RR_Rotation(AVLTreeNode<E> pointer) {
AVLTreeNode<E> a, b;
a=pointer;
b=(AVLTreeNode<E>)a.right;
a.right=b.left;
b.left=a;
if(b.bf==0)//this means the remove cause RR_Rotation
{
b.bf=-1;
//a.bf still be 1
}
else {
a.bf = b.bf = 0;
}
return b;
}
}