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 insert( Comparable x ) { root = insert( x, root ); } /** * Remove from the tree. * @param x the item to remove. * @throws ItemNotFoundException if x is not found. */ public void remove( Comparable x ) { deletedNode = nullNode; root = remove( x, root ); } /** * Find the smallest item in the tree. * @return the smallest item or null if empty. */ public Comparable findMin( ) { if( isEmpty( ) ) return null; AANode ptr = root; while( ptr.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( ) { if( isEmpty( ) ) return null; AANode ptr = root; while( ptr.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 find( Comparable x ) { AANode current = root; nullNode.element = x; for( ; ; ) { if( x.compareTo( current.element ) < 0 ) current = current.left; else if( x.compareTo( current.element ) > 0 ) current = current.right; else if( current != 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 insert( Comparable x, AANode t ) { if( t == nullNode ) t = new AANode( x ); else if( x.compareTo( t.element ) < 0 ) t.left = insert( x, t.left ); else if( x.compareTo( t.element ) > 0 ) t.right = insert( x, t.right ); else throw new DuplicateItemException( x.toString( ) ); t = skew( t ); t = split( t ); 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 remove( Comparable x, AANode t ) { if( t != nullNode ) { // Step 1: Search down the tree and set lastNode and deletedNode lastNode = t; if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left ); else { deletedNode = t; t.right = remove( x, t.right ); } // Step 2: If at the bottom of the tree and // x is present, we remove it if( t == lastNode ) { if( deletedNode == nullNode || x.compareTo( deletedNode.element ) != 0 ) throw new ItemNotFoundException( x.toString( ) ); deletedNode.element = t.element; t = t.right; } // Step 3: Otherwise, we are not at the bottom; rebalance else if( t.left.level < t.level - 1 || t.right.level < t.level - 1 ) { if( t.right.level > --t.level ) t.right.level = t.level; t = skew( t ); t.right = skew( t.right ); t.right.right = skew( t.right.right ); t = split( t ); t.right = split( t.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 skew( AANode t ) { if( t.left.level == t.level ) t = rotateWithLeftChild( t ); 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 split( AANode t ) { if( t.right.right.level == t.level ) { t = rotateWithRightChild( t ); t.level++; } return t; } /** * Rotate binary tree node with left child. */ private static AANode rotateWithLeftChild( AANode k2 ) { AANode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; } /** * Rotate binary tree node with right child. */ private static AANode rotateWithRightChild( AANode k1 ) { AANode k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; } private static class AANode { // Constructors AANode( Comparable 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 AANode( null ); 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 main( String [ ] args ) { AATree t = new AATree( ); final int NUMS = 40000; final int GAP = 307; System.out.println( "Checking... (no bad output means success)" ); t.insert( new Integer( NUMS * 2 ) ); t.insert( new Integer( NUMS * 3 ) ); for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) t.insert( new Integer( i ) ); System.out.println( "Inserts complete" ); t.remove( t.findMax( ) ); for( int i = 1; i < NUMS; i+= 2 ) t.remove( new Integer( i ) ); t.remove( t.findMax( ) ); System.out.println( "Removes complete" ); if( ((Integer)(t.findMin( ))).intValue( ) != 2 || ((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 ) System.out.println( "FindMin or FindMax error!" ); for( int i = 2; i < NUMS; i+=2 ) if( ((Integer)t.find( new Integer( i ) )).intValue( ) != i ) System.out.println( "Error: find fails for " + i ); for( int i = 1; i < NUMS; i+=2 ) if( t.find( new Integer( i ) ) != 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 DuplicateItemException( String message ) { super( message ); } } /** * 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 ItemNotFoundException( String message ) { super( message ); } } ```