А. А. дерева реализации в Java

А. А. Дерево в области компьютерной науки красно-черное дерево с одним дополнительным правилом. В отличие от красно-черные деревья, RED узлы на дереве А. можно добавить только как право subchild. Иными словами, ни красный узел может быть левым subchild. В результате моделирования 2-3 дерева вместо 2-3-4 дерева, что значительно упрощает обслуживание операций.

Следующий код показывает, как реализовать А. А. Дерево в 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 );

    }

}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>