Write a method verifyHeights() of class AvlTree (from the following source code)

Question

Write a method verifyHeights() of class AvlTree (from the following source code) that runs in O(n) time and verifies that the height information in an AVL tree is correctly
maintained and that the balance property is in order.

// AvlTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class AvlTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public AvlTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
System.out.println( "Sorry, remove unimplemented" );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMin( root ).element;
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMax( root ).element;
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if x is found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode<AnyType> insert( AnyType x, AvlNode<AnyType> t )
{
if( t == null )
return new AvlNode<AnyType>( x, null, null );

int compareResult = x.compareTo( t.element );

if( compareResult < 0 )
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x.compareTo( t.left.element ) < 0 )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( compareResult > 0 )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x.compareTo( t.right.element ) > 0 )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private AvlNode<AnyType> findMin( AvlNode<AnyType> t )
{
if( t == null )
return t;

while( t.left != null )
t = t.left;
return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private AvlNode<AnyType> findMax( AvlNode<AnyType> t )
{
if( t == null )
return t;

while( t.right != null )
t = t.right;
return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return true if x is found in subtree.
*/
private boolean contains( AnyType x, AvlNode<AnyType> t )
{
while( t != null )
{
int compareResult = x.compareTo( t.element );

if( compareResult < 0 )
t = t.left;
else if( compareResult > 0 )
t = t.right;
else
return true; // Match
}

return false; // No match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( AvlNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

/**
* Return the height of node t, or -1, if null.
*/
private int height( AvlNode<AnyType> t )
{
return t == null ? -1 : t.height;
}

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private AvlNode<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 )
{
AvlNode<AnyType> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = Math.max( height( k1.left ), k2.height ) + 1;
return k1;
}

/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private AvlNode<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 )
{
AvlNode<AnyType> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.right ), k1.height ) + 1;
return k2;
}

/**
* 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.
* Update heights, then return new root.
*/
private AvlNode<AnyType> doubleWithLeftChild( AvlNode<AnyType> k3 )
{
k3.left = rotateWithRightChild( k3.left );
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.
* Update heights, then return new root.
*/
private AvlNode<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}

private static class AvlNode<AnyType>
{
// Constructors
AvlNode( AnyType theElement )
{
this( theElement, null, null );
}

AvlNode( AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
height = 0;
}

AnyType element; // The data in the node
AvlNode<AnyType> left; // Left child
AvlNode<AnyType> right; // Right child
int height; // Height
}

/** The tree root. */
private AvlNode<AnyType> root;


// Test program
public static void main( String [ ] args )
{
AvlTree<Integer> t = new AvlTree<Integer>( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );

if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 1; i < NUMS; i++ )
if( !t.contains( i ) )
System.out.println( "Find error1!" );
}
}

Explanation / Answer

private static int balance(AvlNode current, AvlNode first_violation, AvlNode second_violation){

AvlNode first = first_violation, second = second_violation;

//checks to make sure that the children are not violating balance

if(((current.left_child != null) && (current.right_child != null)) &&

((current.left_child.height - current.right_child.height < 1) ||

(current.left_child.height - current.right_child.height > -1))){

if(first == null){

if(current.left_child.height - current.right_child.height > 1){

return(balance(current, current.left_child, null));

}

else{

return (balance(current, current.right_child, null));

}

}

else if(second == null){//checking for the grandchild or second violation

if((first.left_child.height - first.right_child.height) > 1){

return(balance(current, first, first.left_child));

}

else if((first.left_child.height - first.right_child.height < -1)){

return(balance(current, first, first.right_child));

}

else{//there is only one violation thus take the child with the greatest height

if(first.left_child.height > first.right_child.height){

return(balance(current, first, first.left_child));

}

else{

return(balance(current, first, first.right_child));

}

}

}

else{//got the nodes referenced to, now evaluate rotations

if((current.left_child.data == first.data) && //double rotation left

(first.left_child.data == second.data)){

AvlNode left = first.left_child;

first.left_child = left.right_child;

left.right_child = first;

first = left;

//then change the heights of first and left

first.height = adjust_height(first, first.height);

left.height = adjust_height(left, left.height);

return 0;

}

else if((current.right_child.data == first.data) && //single rotation left-right

(first.left_child.data == second.data)){

AvlNode left = first.left_child;

AvlNode grandchild = left.right_child;

left.right_child = grandchild.left_child;

grandchild.left_child = left;

first.left_child = grandchild.right_child;

grandchild.right_child = first;

first = grandchild;

//adjust the heights of first and left nodes

first.height = adjust_height(first, first.height);

left.height = adjust_height(left, left.height);

return 0;

}

else if((current.right_child.data == first.data) && //double rotation right

(first.right_child.data == second.data)){

AvlNode right = first.right_child;

first.right_child = right.left_child;

right.left_child = first;

first = right;

//changing heights for first and right nodes

first.height = adjust_height(first, first.height);

right.height = adjust_height(right, right.height);

return 0;

}

else{ //single rotation right-left

AvlNode right = first.right_child;

AvlNode grandchild = right.left_child;

right.left_child = grandchild.right_child;

grandchild.right_child = right;

first.right_child = grandchild.left_child;

grandchild.left_child = first;

first = grandchild;

//adjust the heights of first and right nodes

first.height = adjust_height(first, first.height);

right.height = adjust_height(right, right.height);

return 0;

}

}

}

else{

return 0;//the tree is already balanced...thus do nothing.

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.