Thursday, March 31, 2011

AA - tree implementation in java

An AA tree in computer science is a red-black tree with one additional rule. Unlike red-black trees, RED nodes on an AA tree can only be added as a right subchild. In other words, no RED node can be a left subchild. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations.
The following code shows how to implement a AA tree in Java:
// AATree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert and remove if warranted

/**
 * Implements an AA-tree.
 * Note that all "matching" is based on the compareTo method.
 @author Mark Allen Weiss
 */
public class AATree {
    /**
     * Construct the tree.
     */
    public AATree( ) {
        root = nullNode;
    }
    
    /**
     * Insert into the tree.
     @param x the item to insert.
     @throws DuplicateItemException if x is already present.
     */
    public void insertComparable x ) {
        root = insertx, root );
    }
    
    /**
     * Remove from the tree.
     @param x the item to remove.
     @throws ItemNotFoundException if x is not found.
     */
    public void removeComparable x ) {
        deletedNode = nullNode;
        root = removex, root );
    }
    
    /**
     * Find the smallest item in the tree.
     @return the smallest item or null if empty.
     */
    public Comparable findMin( ) {
        ifisEmpty( ) )
            return null;
        
        AANode ptr = root;
        
        whileptr.left != nullNode )
            ptr = ptr.left;
        
        return ptr.element;
    }
    
    /**
     * Find the largest item in the tree.
     @return the largest item or null if empty.
     */
    public Comparable findMax( ) {
        ifisEmpty( ) )
            return null;
        
        AANode ptr = root;
        
        whileptr.right != nullNode )
            ptr = ptr.right;
        
        return ptr.element;
    }
    
    /**
     * Find an item in the tree.
     @param x the item to search for.
     @return the matching item of null if not found.
     */
    public Comparable findComparable x ) {
        AANode current = root;
        nullNode.element = x;
        
        for; ; ) {
            ifx.compareTocurrent.element )
                current = current.left;
            else ifx.compareTocurrent.element )
                current = current.right;
            else ifcurrent != nullNode )
                return current.element;
            else
                return null;
        }
    }
    
    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( ) {
        root = nullNode;
    }
    
    /**
     * Test if the tree is logically empty.
     @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return root == nullNode;
    }
    
    /**
     * Internal method to insert into a subtree.
     @param x the item to insert.
     @param t the node that roots the tree.
     @return the new root.
     @throws DuplicateItemException if x is already present.
     */
    private AANode insertComparable x, AANode t ) {
        ift == nullNode )
            t = new AANode);
        else ifx.compareTot.element )
            t.left = insertx, t.left );
        else ifx.compareTot.element )
            t.right = insertx, t.right );
        else
            throw new DuplicateItemExceptionx.toString( ) );
        
        t = skew);
        t = split);
        return t;
    }
    
    /**
     * Internal method to remove from a subtree.
     @param x the item to remove.
     @param t the node that roots the tree.
     @return the new root.
     @throws ItemNotFoundException if x is not found.
     */
    private AANode removeComparable x, AANode t ) {
        ift != nullNode ) {
            // Step 1: Search down the tree and set lastNode and deletedNode
            lastNode = t;
            ifx.compareTot.element )
                t.left = removex, t.left );
            else {
                deletedNode = t;
                t.right = removex, t.right );
            }
            
            // Step 2: If at the bottom of the tree and
            //         x is present, we remove it
            ift == lastNode ) {
                ifdeletedNode == nullNode || x.compareTodeletedNode.element != )
                    throw new ItemNotFoundExceptionx.toString( ) );
                deletedNode.element = t.element;
                t = t.right;
            }
            
            // Step 3: Otherwise, we are not at the bottom; rebalance
            else
                ift.left.level < t.level - || t.right.level < t.level - ) {
                ift.right.level > --t.level )
                    t.right.level = t.level;
                t = skew);
                t.right = skewt.right );
                t.right.right = skewt.right.right );
                t = split);
                t.right = splitt.right );
                }
        }
        return t;
    }
    
    /**
     * Skew primitive for AA-trees.
     @param t the node that roots the tree.
     @return the new root after the rotation.
     */
    private static AANode skewAANode t ) {
        ift.left.level == t.level )
            t = rotateWithLeftChild);
        return t;
    }
    
    /**
     * Split primitive for AA-trees.
     @param t the node that roots the tree.
     @return the new root after the rotation.
     */
    private static AANode splitAANode t ) {
        ift.right.right.level == t.level ) {
            t = rotateWithRightChild);
            t.level++;
        }
        return t;
    }
    
    /**
     * Rotate binary tree node with left child.
     */
    private static AANode rotateWithLeftChildAANode k2 ) {
        AANode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }
    
    /**
     * Rotate binary tree node with right child.
     */
    private static AANode rotateWithRightChildAANode k1 ) {
        AANode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }
    
    private static class AANode {
        // Constructors
        AANodeComparable theElement ) {
            element = theElement;
            left    = right = nullNode;
            level   = 1;
        }
        
        Comparable element;      // The data in the node
        AANode     left;         // Left child
        AANode     right;        // Right child
        int        level;        // Level
    }
    
    private AANode root;
    private static AANode nullNode;
    
    static         // static initializer for nullNode
    {
        nullNode = new AANodenull );
        nullNode.left = nullNode.right = nullNode;
        nullNode.level = 0;
    }
    
    private static AANode deletedNode;
    private static AANode lastNode;
    
    // Test program; should print min and max and nothing else
    public static void mainString [ ] args ) {
        AATree t = new AATree( );
        final int NUMS = 40000;
        final int GAP  =   307;
        
        System.out.println"Checking... (no bad output means success)" );
        
        t.insertnew IntegerNUMS * ) );
        t.insertnew IntegerNUMS * ) );
        forint i = GAP; i != 0; i = i + GAP % NUMS )
            t.insertnew Integer) );
        System.out.println"Inserts complete" );
        
        t.removet.findMax( ) );
        forint i = 1; i < NUMS; i+= )
            t.removenew Integer) );
        t.removet.findMax( ) );
        System.out.println"Removes complete" );
        
        
        if( ((Integer)(t.findMin( ))).intValue( ) != ||
                ((Integer)(t.findMax( ))).intValue( ) != NUMS - )
            System.out.println"FindMin or FindMax error!" );
        
        forint i = 2; i < NUMS; i+=)
            if( ((Integer)t.findnew Integer) )).intValue( ) != i )
                System.out.println"Error: find fails for " + i );
        
        forint i = 1; i < NUMS; i+=)
            ift.findnew Integer) )  != null )
                System.out.println"Error: Found deleted item " + i );
    }
}


/**
 * Exception class for duplicate item errors
 * in search tree insertions.
 @author Mark Allen Weiss
 */
public class DuplicateItemException extends RuntimeException {
    /**
     * Construct this exception object.
     */
    public DuplicateItemException( ) {
        super( );
    }
    /**
     * Construct this exception object.
     @param message the error message.
     */
    public DuplicateItemExceptionString message ) {
        supermessage );
    }
}


/**
 * Exception class for failed finds/removes in search
 * trees, hash tables, and list and tree iterators.
 @author Mark Allen Weiss
 */
public class ItemNotFoundException extends RuntimeException {
    /**
     * Construct this exception object.
     */
    public ItemNotFoundException( ) {
        super( );
    }
    
    /**
     * Construct this exception object.
     @param message the error message.
     */
    public ItemNotFoundExceptionString message ) {
        supermessage );
    }
}