package iad4.AVL;
public class AvlNode<E>
{
private E element;
private AvlNode<E> left;
private AvlNode<E> right;
private AvlNode<E> parent;
private int height;
private static StringBuffer buffer;
public AvlNode( )
{
setElement( null );
setHeight( -1 );
}
public AvlNode( E theElement )
{
setElement(theElement);
setLeft( null );
setRight( null );
setParent( null );
setHeight( 0 );
}
/*
* This method is so that the user doesn't have to add the root evertime,
* only the newChild.
*/
public void add( AvlNode<E>x )
{
insert( x, this );
}
/*
* This method does the added. It checks if the node is bigger or smaller then the current.
* This happens with the compare method which the adding node should have. It runs recursief
* until it hits a leaf, then it adds itself.
*/
private void insert( AvlNode<E>newChild, AvlNode<E> root )
{
if(((Comparable<E>) newChild.getElement()).compareTo( root.getElement() ) < 0 )
{
if(root.getLeft() == null)
{
root.setLeft( newChild );
newChild.setParent( root );
System.out.println("Added left " + ((Digit) newChild.getElement()).getNumber() );
}
else
insert(newChild, root.getLeft());
}
else if( ((Comparable<E>) newChild.getElement()).compareTo( root.getElement() ) > 0 )
{
if(root.getRight() == null)
{
root.setRight( newChild );
newChild.setParent( root );
System.out.println("Added Right " + ((Digit) newChild.getElement()).getNumber() );
if( height( this.getRight() ) - height( this.getLeft()) > 1 )
{
System.out.println("Unbalanced");
root = adjustRightTree(root);
}
}
else
insert(newChild, root.getRight());
}
else{
System.out.println("Duplicate");
;
}
root.setHeight(height(root));
}
public AvlNode<E> adjustRightTree(AvlNode<E> node)
{
System.out.println("Unbalanced right!, node which is the ****er: " + ((Digit) node.getElement()).getNumber());
AvlNode<E> root = rotateWithRightChild(node.getParent());
System.out.println(root.preOrderToString());
return root;
}
/*
* This methods runs through the entire tree preOrder style.
* When its done it returns a Stringbuffer containing all the numbers
* in the tree
*/
public String preOrderToString()
{
buffer = new StringBuffer();
buffer.append("Root: " );
preOrder();
return buffer.toString();
}
private void preOrder()
{
buffer.append(((Digit) getElement()).getNumber() + " Height: " + getHeight() + " ");
if( getLeft() != null )
{
buffer.append("Left: ");
getLeft().preOrder();
}
if( getRight() != null )
{
buffer.append("Right: ");
getRight().preOrder();
}
}
/*
* This method return the height of a given node. With this
* method i can check if the tree is balanced
*/
public int height(AvlNode<E> node)
{
int heightLeft = 0;
int heightRight = 0;
if (node == null)
return -1;
if(node.getLeft() != null)
heightLeft = height(node.getLeft()) + 1;
if(node.getRight() != null)
heightRight = height(node.getRight()) + 1;
return Math.max(heightLeft, heightRight);
}
/*
* Rotate a binary tree node with his left child. For AVL trees, this
* is a single rotation for case 1.
*/
private AvlNode<E> rotateWithLeftChild( AvlNode<E> k2 )
{
AvlNode<E> k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight( k2 );
return k1;
}
/*
* Double rotate binary tree node: first left child with its right child;
* then node k3 with new left child. For AVL trees, this is a double rotation
* for case 2.
*/
private AvlNode<E> doubleRotateWithLeftChild( AvlNode<E> k3 )
{
k3.setLeft(rotateWithRightChild( k3.getLeft()));
return rotateWithLeftChild( k3 );
}
/*
* Double rotate binary tree node: first right child with its left child;
* then node k1 with new right child. For AVL trees, this is a double rotation
* for case 3.
*/
private AvlNode<E> doubleRotateWithRightChild( AvlNode<E> k1 )
{
k1.setRight( rotateWithLeftChild( k1.getRight() ));
return rotateWithRightChild( k1 );
}
/*
* Rotate binary tree node with right child. For AVL trees this is a
* single rotation for case 4.
*/
private AvlNode<E> rotateWithRightChild( AvlNode<E> k1)
{
AvlNode<E> k2 = k1.getRight();
k1.setRight( k2.getLeft() );
k2.setLeft( k1 );
return k2;
}
/*
* Getters And setters!
*/
... Niet interressant
}
hoop dat iemand het ziet!
. Het programma werkt en doet wat het moet doen maar ik wil dit snappen. Ga ik te ver met casten of wat?
