AVL tree balance factor
hi there,
At University we need to add an algorithm to calculate the balance factor of each node in an AVL treewithout using the hight to calculate it.
All we are alloud to use is the int bal attribute and the matchingint getBalance() andchageBalance(int bal) Methods supplied in the node class.
My attempt sometimes works and mostly doesn't. Heres what i wrote to the end of theNode insertNode(char key, Node partTree) Method:
if(partTree.getNodeLeft()==null && partTree.getNodeRight()==null)
{
System.out.print("Case 1 (0,0) | ");
partTree.bal=0;
}
elseif(partTree.getNodeLeft()!=null && partTree.getNodeRight()==null)
{
System.out.print("Case 2 (1,0) | ");
partTree.changeBalance(-1);
}
elseif(partTree.getNodeLeft()==null && partTree.getNodeRight()!=null)
{
System.out.print("Case 3 (0,1) | ");
partTree.changeBalance(+1);
}
else
{
System.out.print("Case 4 (1,1) | ");
partTree.bal = partTree.getNodeRight().getBalance() + partTree.getNodeLeft().getBalance();
}
System.out.println("["+partTree.getKey() +"] | " + partTree.getBalance());
Message was edited by:
Nark
