java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4091
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
AA-Tree Implementation in Java E-mail
User Rating: / 73
PoorBest 

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 );
    }
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.