Adavanced Data Structures project to implement a string based AVL tree

prog2.java

/**
 * File:       prog2.java
 * Package:    None
 * Project:    COMP_282
 * Date:       Mar 10, 2015, 9:30:11 PM
 * Purpose:    To implement a string AVL tree
 * @author     Kory Dondzila
 * @version    "%I%, %G%"
 * Copyright:  2015
 */

/**
 * Node class for a string based AVL tree
 */
class StringAVLNode
{
	/**
	 * The node data
	 */
	private String item;
	
	/**
	 * Balance of the node
	 */
	private int balance;
	
	/**
	 * Left and right nodes
	 */
	private StringAVLNode left, right;
	
	/**
	 * AVLNode constructor
	 * @param str the string to set item to
	 */
	public StringAVLNode(String str)
	{
		this.item = str;
		balance = 0;
		left = null;
		right = null;
	}
	
	/**
	 * @return the balance
	 */
	public int getBalance()
	{
		return this.balance;
	}

	/**
	 * @param balance the balance to set
	 */
	public void setBalance( int balance )
	{
		this.balance = balance;
	}

	/**
	 * @return the item
	 */
	public String getItem()
	{
		return this.item;
	}

	/**
	 * @return the left
	 */
	public StringAVLNode getLeft()
	{
		return this.left;
	}

	/**
	 * @param left the left to set
	 */
	public void setLeft( StringAVLNode left )
	{
		this.left = left;
	}

	/**
	 * @return the right
	 */
	public StringAVLNode getRight()
	{
		return this.right;
	}

	/**
	 * @param right the right to set
	 */
	public void setRight( StringAVLNode right )
	{
		this.right = right;
	}
}

/**
 * The string based AVL tree class
 */
class StringAVLTree
{
	/**
	 * The root node
	 */
	private StringAVLNode root;
	
	
	/**
	 * Default constructor
	 */
	public StringAVLTree()
	{
		root = null;
	}
	
	/**
	 * @return the root
	 */
	public StringAVLNode getRoot()
	{
		return this.root;
	}

	/**
	 * Rotate the node to the right
	 * @param t the node to rotate around
	 * @return the rotated node
	 */
	private static StringAVLNode rotateRight( StringAVLNode t )
	{
		StringAVLNode temp = t.getLeft();
		
		t.setLeft( temp.getRight() );
		temp.setRight( t );
		
		return temp;
	}
	
	/**
	 * Rotate the node to the left
	 * @param t the node to rotate around
	 * @return the rotated node
	 */
	private static StringAVLNode rotateLeft( StringAVLNode t )
	{
		StringAVLNode temp = t.getRight();
		
		t.setRight( temp.getLeft() );
		temp.setLeft( t );
		
		return temp;
	}
	
	/**
	 * Double rotation with respect to right child
	 * @param t the node to rotate around
	 * @return the rotated node
	 */
	private static StringAVLNode doubleRotateWithRight( StringAVLNode t )
	{
		t.setRight( rotateRight( t.getRight() ) );
		t = rotateLeft( t );
		
		adjustBalances( t );	// Adjust balances after rotating
		
		return t;
	}
	
	/**
	 * Double rotation with respect to left child
	 * @param t the node to rotate around
	 * @return the rotated node
	 */
	private static StringAVLNode doubleRotateWithLeft( StringAVLNode t )
	{
		t.setLeft( rotateLeft( t.getLeft() ) );
		t = rotateRight( t );
		
		adjustBalances( t );
		
		return t;
	}
	
	/**
	 * Adjusts balances for double rotations
	 * @param t the node to adjust balances on
	 */
	private static void adjustBalances( StringAVLNode t )
	{
		if ( t.getBalance() == 0 )
		{
			t.getLeft().setBalance( 0 );
			t.getRight().setBalance( 0 );
		}
		else if ( t.getBalance() == -1 )
		{
			t.setBalance( 0 );
			t.getLeft().setBalance( 0 );
			t.getRight().setBalance( 1 );
		}
		else
		{
			t.setBalance( 0 );
			t.getLeft().setBalance( -1 );
			t.getRight().setBalance( 0 );
		}
	}
	
	/**
	 * Handles rotations and re-balancing after a node deletion
	 * @param t the node to re-balance
	 * @return the re-blanced node
	 */
	private static StringAVLNode deletionRebalance( StringAVLNode t )
	{
		 if ( t.getBalance() == 2 ) // Rotate on the right?
         {
             if ( t.getRight().getBalance() == 1 ) // Single rotate?
             {
             	t = rotateLeft( t );
             	t.setBalance( 0 );
             	t.getLeft().setBalance( 0 );
             }
             else if ( t.getRight().getBalance() == 0 )
             {
             	t = rotateLeft( t );
             	t.setBalance( -1 );
             	t.getLeft().setBalance( 1 );
             }
             else // Double rotate
             {
             	t = doubleRotateWithRight( t );
             }
         }
		 else if ( t.getBalance() == -2 ) // Rotate on the left?
         {
             if ( t.getLeft().getBalance() == -1 ) // Single rotate?
             {
             	t = rotateRight( t );
             	t.setBalance( 0 );
             	t.getRight().setBalance( 0 );
             }
             else if ( t.getLeft().getBalance() == 0 ) // Single rotate?
             {
             	t = rotateRight( t );
             	t.setBalance( 1 );
             	t.getRight().setBalance( -1 );
             }
             else // Double rotate
             {
             	t = doubleRotateWithLeft( t );
             }
         }
		 
		 return t;
	}
	
	/**
	 * Gets height of tree
	 * @return the height
	 */
	public int height()
	{
		return height( root, 0 );
	}
	
	/**
	 * Recursively finds the height of the tree
	 * @param t the node to get height of
	 * @param count current height
	 * @return current height
	 */
	private static int height( StringAVLNode t, int count )
	{
		if ( t != null )
		{
			if ( t.getBalance() <= 0 )  // Go to larger height
			{
				count = height( t.getLeft(), count + 1 );
			}
			else
			{
				count = height( t.getRight(), count + 1 );
			}
		}
		
		return count;
	}
	
	/**
	 * Gets the number of leaves
	 * @return the number of leaves
	 */
	public int leafCt()
	{
		return leafCt( root );
	}
	
	/**
	 * Recursively gets the number of leaves
	 * @param t the node to get leaves on
	 * @return the number of leaves
	 */
	private static int leafCt( StringAVLNode t )
	{
		int count = 0;
		
		if ( t != null )
		{
			// Increment count on leaf nodes only
    		if ( t.getLeft() == null && t.getRight() == null )
    		{
    			count++;
    		}
    		else
    		{
    			count = leafCt( t.getLeft() ) + leafCt( t.getRight() );
    		}
		}
		
		return count;
	}
	
	/**
	 * Gets the number of sticks, nodes with only one non-null child
	 * @return the number of sticks
	 */
	public int stickCt()
	{
		return stickCt( root );
	}
	
	/**
	 * Recursively gets the number of sticks
	 * @param t the node to get sticks on
	 * @return the number of sticks
	 */
	private static int stickCt( StringAVLNode t )
	{
		int count = 0;
		
		if ( t != null )
		{
			// Increment count only on sticks
    		if ( ( t.getLeft() != null && t.getRight() == null ) ||
    				( t.getLeft() == null && t.getRight() != null ) )
    		{
    			count++;
    		}
    		else
    		{
    			count = stickCt( t.getLeft() ) + stickCt( t.getRight() );
    		}
		}
		
		return count;
	}
	
	/**
	 * Gets the number of perfectly balanced nodes
	 * @return the number of perfectly balanced nodes
	 */
	public int balanced()
	{
		return balanced( root );
	}
	
	/**
	 * Recursively gets the number of balanced nodes
	 * @param t the node to get balanced nodes on
	 * @return the number of balanced nodes
	 */
	private static int balanced( StringAVLNode t )
	{
		int count = 0;
		
		if ( t != null )
		{
			if ( t.getBalance() == 0 )
			{
				count++;
			}
			
			count += balanced( t.getLeft() ) + balanced( t.getRight() );
		}
		
		return count;
	}
	
	/**
	 * Gets the in-order successor
	 * @param str the string to find in-order successor of
	 * @return the in-order successor or null if there is none or str is not in the tree
	 */
	public String successor( String str )
	{
		StringAVLNode found = null;
		String val;
		
		found = successor( str, root, null );
		
		val = found != null ? found.getItem() : null;
		
		return val;
	}
	
	/**
	 * Recursively finds the in-order successor
	 * @param str the string to find in-order successor of
	 * @param t the current node
	 * @param max the current in-order successor
	 * @return the in-order successor
	 */
	private static StringAVLNode successor( String str, StringAVLNode t, StringAVLNode max )
	{
		StringAVLNode found = null;
		
		if ( t != null )
		{
			// Recursively look for node containing str only changing max when
			// going left
			if ( str != null && str.compareToIgnoreCase( t.getItem() ) < 0 )
			{
				found = successor( str, t.getLeft(), t );
			}
			else if ( str != null && str.compareToIgnoreCase( t.getItem() ) > 0 )
			{
				found = successor( str, t.getRight(), max );
			}
			else
			{
				// Once node is found then get its in-order successor
				if ( str != null /*&& t.getRight() != null*/ )
				{
					str = null;
					found = successor( str, t.getRight(), max );
				}
				else
				{
					found = successor( str, t.getLeft(), t );
				}
			}
		}
		else if ( str == null )
		{
			found = max;
		}
		
		return found;
	}
	
	/**
	 * Inserts a new node with str if it doesn't exist
	 * @param str the string to insert
	 */
	public void insert( String str )
	{
		root = insert( str, root );
	}
	
	/**
	 * Recursively inserts a new node in the tree
	 * @param str the string to insert
	 * @param t the node to insert to
	 * @return the node t
	 */
	private static StringAVLNode insert( String str, StringAVLNode t )
	{
		if ( t == null ) // easiest case – inserted node goes here
		{
			t = new StringAVLNode( str );
		}
		else if ( str.compareToIgnoreCase( t.getItem() ) < 0 ) // str is smaller than this node – go left
		{
			Integer oldBalance;
			
			// Get oldbalance if child on left
			if ( t.getLeft() == null )
			{
				oldBalance = null;
			}
			else
			{
				oldBalance = t.getLeft().getBalance();
			}
			
			t.setLeft( insert( str, t.getLeft() ) );  // Insert to the left
			Integer newBalance = t.getLeft().getBalance();  // Get newbalance
			
			if ( ( oldBalance == null && newBalance == 0 ) || // Did height increase?
					( oldBalance == 0 && newBalance != 0 ) )
			{
				t.setBalance( t.getBalance() - 1 );  // Decrease balance
				
    			if ( t.getBalance() == -2 ) // out of balance – must rotate and rebalance
    			{
    				if ( t.getLeft().getBalance() == -1 ) // single rotation
    				{
    					t = rotateRight( t );
    					t.setBalance( 0 );
    					t.getRight().setBalance( 0 );
    				}
    				else // double rotation
    				{
    					t = doubleRotateWithLeft( t );
					}
    			}
			}
		}
		else if ( str.compareToIgnoreCase( t.getItem() ) > 0 ) // str is larger than this node – go right
		{
			Integer oldBalance;
			
			// Get oldbalance if child on right
			if ( t.getRight() == null )
			{
				oldBalance = null;
			}
			else
			{
				oldBalance = t.getRight().getBalance();
			}
			
			t.setRight( insert( str, t.getRight() ) );	// Insert to the right
			Integer newBalance = t.getRight().getBalance();  // Get newbalance
			
			if ( ( oldBalance == null && newBalance == 0 ) || // Did height increase?
					( oldBalance == 0 && newBalance != 0 ) )
			{
				t.setBalance( t.getBalance() + 1 );
				
    			if ( t.getBalance() == 2 ) // out of balance – must rotate and rebalance
    			{
    				if ( t.getRight().getBalance() == 1 ) // single rotation
    				{
    					t = rotateLeft( t );
    					t.setBalance( 0 );
    					t.getLeft().setBalance( 0 );
    				}
    				else // double rotation
    				{
    					t = doubleRotateWithRight( t );
					}
    			}
			}
		}
		
		return t;
	}
	
    /**
     * Delete node that contains str if it exists
     * @param str the string to delete from the tree
     */
    public void delete( String str )
    {
    	root = delete( str, root );
    }
    
    /**
     * Recursively deletes the node from the tree
     * @param str the string to delete
     * @param t the current node to delete from
     * @return the current node
     */
    private StringAVLNode delete( String str, StringAVLNode t )
    {
    	if ( t == null )
    	{
    		// Do nothing if it is not in the tree
    	}
    	else if ( str.compareToIgnoreCase( t.getItem() ) < 0 ) // str is smaller than this node – go left
    	{
    		Integer oldBalance;
    		
    		// Get oldbalance if child on left
            if ( t.getLeft() == null )
            {
            	oldBalance = null;
            }
            else
            {
            	oldBalance = t.getLeft().getBalance();
            }
            
            t.setLeft( delete( str, t.getLeft() ) );  // Delete on left
            Integer newBalance;
            
            // Get newbalance if child on left
            if ( t.getLeft() == null )
            {
            	newBalance = null;
            }
            else
            {
            	newBalance = t.getLeft().getBalance();
            }
            
            if ( oldBalance != null &&	// Did node exist and did height decrease?
            		( ( oldBalance == 0 && newBalance == null ) ||
            				( oldBalance != 0 && newBalance == 0 ) ) )
            {
            	t.setBalance( t.getBalance() + 1 );  // Increase balance then possibly rotate
                t = deletionRebalance( t );
            }
    	}
        else if ( str.compareToIgnoreCase( t.getItem() ) > 0 )  // str is larger than this node – go right
        {
    		Integer oldBalance;
    		
    		// Get oldbalance if child on right
            if ( t.getRight() == null )
            {
            	oldBalance = null;
            }
            else
            {
            	oldBalance = t.getRight().getBalance();
            }
            
            t.setRight( delete( str, t.getRight() ) );  // Delete on right
            Integer newBalance;
            
            // Get newbalance if child on right
            if ( t.getRight() == null )
            {
            	newBalance = null;
            }
            else
            {
            	newBalance = t.getRight().getBalance();
            }
            
            if ( oldBalance != null &&  // Did node exist and did height decrease?
            		( ( oldBalance == 0 && newBalance == null ) ||
            				( oldBalance != 0 && newBalance == 0 ) ) )
            {
            	t.setBalance( t.getBalance() - 1 );  // Decrease balance and possibly rotate
                t = deletionRebalance( t );
            }
        }
        else // Node to be deleted
        {
            if ( t.getLeft() == null && t.getRight() == null )  // no children, remove
            {
            	t = null;
            }
            else if ( t.getLeft() == null || t.getRight() == null ) // one child, replace
            {
            	t = t.getLeft() != null ? t.getLeft() : t.getRight();
            }
            else  // Two children
            {
            	Integer oldBalance;
            	
            	// Get oldbalance if child on left
                if ( t.getLeft() == null )
                {
                	oldBalance = null;
                }
                else
                {
                	oldBalance = t.getLeft().getBalance();
                }
                
            	t = replace( t, null, t.getLeft() );  // Replace with in-order predecessor
                Integer newBalance;
                
                // Get newbalance if child on left
                if ( t.getLeft() == null )
                {
                	newBalance = null;
                }
                else
                {
                	newBalance = t.getLeft().getBalance();
                }
                
                if ( oldBalance != null &&  // Did node exist and did height decrease?
                		( ( oldBalance == 0 && newBalance == null ) ||
                				( oldBalance != 0 && newBalance == 0 ) ) )
                {
                	t.setBalance( t.getBalance() + 1 );  // Increase balance and possibly rotate
                    t = deletionRebalance( t );
                }
            }
        }
    	
    	return t;
    }
    
    /**
     * Recursively replaces node t with its in-order predecessor
     * @param t the node to delete
     * @param prev the previous current node
     * @param replacement the current node to replace t with
     * @return the current node
     */
    private StringAVLNode replace( StringAVLNode t, StringAVLNode prev, StringAVLNode replacement )
    {
        if ( replacement.getRight() == null ) // at in-order predecessor
        {
        	StringAVLNode temp = null;
        	
            if ( prev != null )  // if replacement node is NOT the child
            {
            	temp = replacement.getLeft();  // will become prev's right
            }
            else
            {
            	temp = replacement.getLeft();
            }
            
            // Replacing t 
            replacement.setRight( t.getRight() );  // attach t's right
            replacement.setBalance( t.getBalance() );  // need to have t's balance
            t = replacement;  // replace t
            
            replacement = temp;
        }
        else  // Not yet at in-order predecessor
        {
        	Integer oldBalance;
        	
        	// Get oldbalance if child on right
            if ( replacement.getRight() == null )
            {
            	oldBalance = null;
            }
            else
            {
            	oldBalance = replacement.getRight().getBalance();
            }
            
        	t = replace( t, replacement, replacement.getRight() );  // replace with in-order predecessor
            Integer newBalance;
            
            // Get newbalance if child on right
            if ( replacement.getRight() == null )
            {
            	newBalance = null;
            }
            else
            {
            	newBalance = replacement.getRight().getBalance();
            }
            
            if ( oldBalance != null &&  // Did node exist and did height decrease?
            		( ( oldBalance == 0 && newBalance == null ) ||
            				( oldBalance != 0 && newBalance == 0 ) ) )
            {
            	// Decrease balance and possibly rotate
            	replacement.setBalance( replacement.getBalance() - 1 );
            	replacement = deletionRebalance( replacement );
            }
        }
        
        // Properly re-attach nodes back up tree, since t is returned
        // this must get done in the case where a rotation happened
        if ( prev != null )  // Not yet at top recursive call so set prev's right
        {
        	prev.setRight( replacement );
        }
        else  // At top recursive call, set t's left
        {
        	t.setLeft( replacement );
        }
        
        return t;
    }
    
    /**
     * @return the author
     */
    public static String myName()
    {
    	return "Kory A. Dondzila";
    }
}