AVLTree
13564 단어 JavaScriptJUnitHSQLDB
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;
}
}
지금 은 간단 한 테스트 만 했 는데...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
기초 정리 - 1문자 (String) 숫자 (Number) 불린 (Boolean) null undefined 심볼 (Symbol) 큰정수 (BigInt) 따옴표로 묶어 있어야 함 Not-A-Number - 숫자 데이터 / 숫자로 표...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.