最近小看了下hsqldb的源码，发现它的索引时用AVLTree实现的，为了更深刻理解AVLTree,自己模仿hsqldb的AVLTree写了一个小平衡二叉树。目前不支持并发，好像java的map 里面有个树形结构实现。
public class AVLNode {
public AVLNode left=null;
public AVLNode right=null;
public AVLNode parent=null;
public Comparable key;
public Object value;
public int balance=0;
public AVLNode(Comparable key,Object value)
{
this.key=key;
this.value=value;
}
public boolean isFromLeft()
{
return this.parent.left==this;
}
public void childAs(boolean isLeft,AVLNode newParent)
{
this.parent=newParent;
if(isLeft)
newParent.left=this;
else
newParent.right=this;
}
public AVLNode getSmallest()
{
AVLNode node=this;
AVLNode tmpNode=this;
while(tmpNode!=null)
{
node=tmpNode;
tmpNode=tmpNode.left;
}
return node;
}
public AVLNode getLargest()
{
AVLNode node=this;
AVLNode tmpNode=this;
while(tmpNode!=null)
{
node=tmpNode;
tmpNode=tmpNode.right;
}
return node;
}
}
import java.util.Iterator;
public class AVLTree {
private AVLNode root=null;
public AVLNode getRoot() {
return root;
}
public void insert(AVLNode toInsert)
{
//whether to check this node's child
if(toInsert.left!=null||toInsert.right!=null)
;
if(root==null)
root=toInsert;
//locate this node's position
AVLNode tmpNode=root;
AVLNode insertParent=null;<script type="text/javascript"><!--mce:0--></script>
while(tmpNode!=null)
{
int compare=toInsert.key.compareTo(tmpNode.key);
if(compare==0)
return;
else if(compare==-1)
{
insertParent=tmpNode;
tmpNode=tmpNode.left;
}
else
{
insertParent=tmpNode;
tmpNode=tmpNode.right;
}
}
//get the left or right
boolean isLeft=toInsert.key.compareTo(insertParent.key)==-1?true:false;
toInsert.childAs(isLeft, insertParent);
AVLNode toBalance=traceBackRefreshBalanceInsert(toInsert);
if(toBalance!=null)
balance(toBalance);
}
//trace back to refresh the balances and find where need to rotate
private AVLNode traceBackRefreshBalanceInsert(AVLNode traceNode)
{
int childFlag;//from left or right -1 left 1 right
while(traceNode!=root)
{
childFlag=traceNode.isFromLeft()?-1:1;
traceNode.parent.balance+=childFlag;//refresh
switch(Math.abs(traceNode.parent.balance))
{
case 0://this subTree is balanced
return null;
case 1://continue refresh
break;
case 2://subTree traceNode.parent.balance is not balance!
return traceNode.parent;
}
traceNode=traceNode.parent;
}
return null;
}
private AVLNode traceBackRefreshBalanceDelete(AVLNode traceNode)
{
AVLNode tmpNode=traceNode;
int isFromLeft;
while(tmpNode!=root)
{
isFromLeft=tmpNode.isFromLeft()?-1:1;
tmpNode.parent.balance-=isFromLeft;
switch(Math.abs(tmpNode.parent.balance))
{
case 0:
break;
case 1:
return null;
case 2:
return tmpNode.parent;
}
}
return null;
}
//balance the tree
private void balance(AVLNode toBalance)
{
if(toBalance.balance<0)
{
if(toBalance.left.balance<=0)//LL right rotate
{
AVLNode toBalanceLeftChild=toBalance.left;
AVLNode toBalanceNewLeftChild=toBalance.left.right;
toBalance.balance=0;
toBalance.left.balance=0;
if(toBalance.parent==null)
{
root=toBalanceLeftChild;
toBalanceLeftChild.parent=null;
}
else
toBalanceLeftChild.childAs(toBalance.isFromLeft(), toBalance.parent);
toBalance.childAs(false, toBalanceLeftChild);
if(toBalanceNewLeftChild!=null)
toBalanceNewLeftChild.childAs(true, toBalance);
}
else//LR left-right rotate
{
AVLNode newLeftChild=toBalance.left;
AVLNode newRoot=toBalance.left.right;
AVLNode newLeftChildRight=toBalance.left.right.left;
AVLNode newRightChildLeft=toBalance.left.right.right;
newLeftChild.balance=0;
newRoot.balance=0;
if(toBalance.parent==null)
{
root=newRoot;
newRoot.parent=null;
}
else
newRoot.childAs(toBalance.isFromLeft(), toBalance.parent);
newLeftChild.childAs(true, newRoot);
toBalance.childAs(false, newRoot);
if(newLeftChildRight!=null)
newLeftChildRight.childAs(false, newLeftChild);
if(newRightChildLeft!=null)
newRightChildLeft.childAs(true, toBalance);
}
}
else
{
if(toBalance.right.balance>=0)//RR left rotate
{
AVLNode toBalanceRightChild=toBalance.right;
AVLNode toBalanceNewRightChild=toBalance.right.left;
toBalance.balance=0;
toBalance.right.balance=0;
if(toBalance.parent==null)
{
toBalanceRightChild.parent=null;
root=toBalanceRightChild;
}
else
toBalanceRightChild.childAs(toBalance.isFromLeft(), toBalance.parent);
toBalance.childAs(true, toBalanceRightChild);
if(toBalanceNewRightChild!=null)
toBalanceNewRightChild.childAs(false, toBalance);
}
else//RL right-left rotate
{
AVLNode newRightChild=toBalance.right;
AVLNode newRoot=toBalance.right.left;
AVLNode newLeftChildRight=toBalance.right.left.left;
AVLNode newRightChildLeft=toBalance.right.left.right;
newRightChild.balance=0;
newRoot.balance=0;
if(toBalance.parent==null)
{
root=newRoot;
newRoot.parent=null;
}
else
newRoot.childAs(toBalance.isFromLeft(), toBalance.parent);
newRightChild.childAs(false, newRoot);
toBalance.childAs(true, newRoot);
if(newLeftChildRight!=null)
newLeftChildRight.childAs(false, toBalance);
if(newRightChildLeft!=null)
newRightChildLeft.childAs(true, newRightChild);
}
}
}
public AVLNode delete(Comparable key)
{
AVLNode toDelete=getAVLNodeByKey(key);
if(toDelete==null)
return null;
if(toDelete==root&&toDelete.left==null&&toDelete.right==null)
{
root=null;
return root;
}
//begin replace to delete node with a node
//this node is the deeper subTree's smallest node of the right subTree
//or the largest node of the left subTree
AVLNode toReplace;
AVLNode toBalance;
int compare=toDelete.balance;
if(compare<=0)
{
toReplace=toDelete.left.getLargest();
toBalance=traceBackRefreshBalanceDelete(toReplace);
if(toReplace.left!=null)
toReplace.left.childAs(false, toReplace.parent);
}
else
{
toReplace=toDelete.right.getSmallest();
toBalance=traceBackRefreshBalanceDelete(toReplace);
if(toReplace.right!=null)
toReplace.right.childAs(true, toReplace.parent);
}
if(toDelete.left!=null)
toDelete.left.childAs(true, toReplace);
if(toDelete.right!=null)
toDelete.right.childAs(false, toReplace);
toReplace.balance=toDelete.balance;
//set new root if toDelete is the root
if(toDelete.parent==null)
{
toReplace.parent=null;
root=toReplace;
}
else
{
toReplace.childAs(toDelete.isFromLeft(), toDelete.parent);
}
//balance
if(toBalance!=null)
balance(toBalance);
//refresh balance again
AVLNode tmpNode=toBalance;
while(tmpNode.parent!=null)
{
int isFromLeft;
isFromLeft=tmpNode.isFromLeft()?-1:1;
tmpNode.parent.balance-=isFromLeft;
tmpNode=tmpNode.parent;
}
//clear this node
toDelete.left=toDelete.right=toDelete.parent=null;
return toDelete;
}
public AVLNode getAVLNodeByKey(Comparable key)
{
AVLNode tmpNode=root;
while(tmpNode!=null)
{
switch(key.compareTo(tmpNode.key))
{
case 0:
return tmpNode;
case -1:
tmpNode=tmpNode.left;
break;
case 1:
tmpNode=tmpNode.right;
break;
}
}
return null;
}
}
import junit.framework.TestCase;
public class TestAVLTree extends TestCase{
AVLTree tree=new AVLTree();
public void testInsertRR()
{
tree=new AVLTree();
tree.insert(new AVLNode(1,1));
assertEquals(1, tree.getRoot().value);
tree.insert(new AVLNode(2,2));
assertEquals(1, tree.getRoot().value);
assertEquals(2, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().right.balance);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertLL()
{
tree=new AVLTree();
tree.insert(new AVLNode(3,3));
assertEquals(3, tree.getRoot().value);
tree.insert(new AVLNode(2,2));
assertEquals(3, tree.getRoot().value);
assertEquals(2, tree.getRoot().left.value);
assertEquals(-1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertRL()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
assertEquals(2, tree.getRoot().value);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().right.balance);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertLR()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
assertEquals(2, tree.getRoot().value);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(-1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testGetNode()
{
tree=newTree();
assertEquals(6,tree.getAVLNodeByKey(6).value);
}
public void testHeadAndTail()
{
tree=newTree();
assertEquals(11,tree.getRoot().getLargest().value);
assertEquals(1,tree.getRoot().getSmallest().value);
}
public void testDeleteRL()
{
tree=newTree();
assertEquals(4,tree.getRoot().key);
assertNull(tree.getRoot().parent);
assertEquals(5,tree.getRoot().right.getSmallest().key);
assertEquals(1,tree.getRoot().balance);
tree.delete(tree.getRoot().key);
assertEquals(5,tree.getRoot().key);
assertEquals(0,tree.getRoot().balance);
}
private AVLTree newTree()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
tree.insert(new AVLNode(1,1));
tree.insert(new AVLNode(3,3));
tree.insert(new AVLNode(4,4));
tree.insert(new AVLNode(5,5));
tree.insert(new AVLNode(6,6));
tree.insert(new AVLNode(7,7));
tree.insert(new AVLNode(11,11));
return tree;
}
}
目前只做了简单的测试。。。
分享到：
相关推荐
使用C++实现的AVLTree自平衡二叉树，支持动态插入与删除操作，供C++数据结构课程学习与交流使用。
本设计实现了AVLTree的所有的实现功能，也包括BinSTree与AVLTree的转换
一个avltree的简单实现，便于了解avltree的结构及应用
AVL Tree 的代码实例，包括插入和删除节点操作。
avl tree 中的各种旋转
这是一个用C实现的AVL tree，带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree，一共是70000多个文件和目录，耗时大约是5-7秒
AVL Tree source code
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is...
AVL tree using node from data structure and algorithm java class, create a minimum AVL tree with minimum number of nodes at given high
04-树4. Root of AVL Tree (25)。 AVL树的旋转，Devc的工程文件。
avl tree implementation
AVL tree implementation in java
avltree的c代码实现，没有错，放心下载
自己写的平衡树的构建及相关操作
AVL tree with insertion,deletion and balancing height
自己写的AVLtree，大家看着用吧，是浙大网课上的同步作业
AVL Tree implementation
Java代码实现，从文件中读取数据，根据AVL树的构建规则，构建一棵AVL树（平衡二叉树），并输出平均查找长度ASL。
AVL tree AVL树 完全平衡树基本操作
AVLTREE，数据结构中AVL树的C语言实现