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;
}
}