AVLTree
最近小看了下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;elsenewParent.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 childif(toInsert.left!=null||toInsert.right!=null);if(root==null)root=toInsert;//locate this node's positionAVLNode 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 rotateprivate AVLNode traceBackRefreshBalanceInsert(AVLNode traceNode){int childFlag;//from left or right -1 left 1 rightwhile(traceNode!=root){childFlag=traceNode.isFromLeft()?-1:1;traceNode.parent.balance+=childFlag;//refreshswitch(Math.abs(traceNode.parent.balance)){case 0://this subTree is balancedreturn null;case 1://continue refreshbreak;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 treeprivate 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;}elsetoBalanceLeftChild.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;}elsenewRoot.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;}elsetoBalanceRightChild.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;}elsenewRoot.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 subTreeAVLNode 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 rootif(toDelete.parent==null){toReplace.parent=null;root=toReplace;}else{toReplace.childAs(toDelete.isFromLeft(), toDelete.parent);}//balanceif(toBalance!=null)balance(toBalance);//refresh balance againAVLNode tmpNode=toBalance;while(tmpNode.parent!=null){int isFromLeft;isFromLeft=tmpNode.isFromLeft()?-1:1;tmpNode.parent.balance-=isFromLeft;tmpNode=tmpNode.parent;}//clear this nodetoDelete.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;}} 目前只做了简单的测试。。。
页:
[1]