Красное дерево черный осуществления в Java

Красно-черное дерево является одним из видов самобалансирующейся бинарных деревьев поиска, структуры данных, используемые в информатике, как правило, используются для реализации ассоциативных массивов. Оригинальное сооружение было изобретено в 1972 году Рудольф Байер, который назвал их "симметричного бинарного B-деревья", но приобрел свое современное название в документе, в 1978 году Leo J. Guibas и Роберт Sedgewick. Это сложная, но имеет хорошие наихудшее время для осуществления своей деятельности и является эффективной на практике: он может поиска, вставки и удаления в O (Вход п), где N это количество элементов в дереве.

Красно-черное дерево представляет собой особый тип бинарного дерева, которое является структура, используемая в компьютерной науке организовать штук сопоставимых данных, такие как номера. Каждая часть данных хранится в узле. Один из узлов всегда функционирует как наша отправная точка, а не ребенка любого узла, мы называем это корневой узел или корень. Она до двух "детей", другие узлы, к которым он подключается. Каждая из этих детей могут иметь детей от своей собственной, и так далее. Корневого узла, таким образом, путь, соединяющий его на любой другой узел в дереве.

Если узел не имеет детей, мы называем его конечного узла, так как интуитивно он находится на периферии этого дерева. Поддерева часть дерева, которая может быть достигнута с определенными узлами, которые считаются само дерево. В красно-черные деревья, предполагается, что оставляет быть нулевым или пустым.

Как красно-черные деревья, также бинарные деревья поиска, которые они должны соблюдать ограничения, что каждый узел содержит значение большее или равное для всех узлов в левом поддерева, и меньше или равны для всех узлов, в своем праве поддерева. Это позволяет быстро искать дерево для заданного значения.

Следующий код показывает, как реализовать красно-черное дерево Java:



// RedBlackTree class


//


// CONSTRUCTION: with a negative infinity sentinel


//


// ******************PUBLIC OPERATIONS*********************


// void insert( x )       --> Insert x


// void remove( x )       --> Remove x (unimplemented)


// 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


// void printTree( )      --> Print all items


// ******************ERRORS********************************


// Exceptions are thrown by insert if warranted and remove.





/**


 * Implements a red-black tree.


 * Note that all "matching" is based on the compareTo method.


 * @author Mark Allen Weiss


 */


public class RedBlackTree {


    /**


     * Construct the tree.


     */


    public RedBlackTree( ) {


        header      = new RedBlackNode( null );


        header.left = header.right = nullNode;


    }


    


    /**


     * Compare item and t.element, using compareTo, with


     * caveat that if t is header, then item is always larger.


     * This routine is called if is possible that t is header.


     * If it is not possible for t to be header, use compareTo directly.


     */


    private final int compare( Comparable item, RedBlackNode t ) {


        if( t == header )


            return 1;


        else


            return item.compareTo( t.element );


    }


    


    /**


     * Insert into the tree.


     * @param item the item to insert.


     * @throws DuplicateItemException if item is already present.


     */


    public void insert( Comparable item ) {


        current = parent = grand = header;


        nullNode.element = item;


        


        while( compare( item, current ) != 0 ) {


            great = grand; grand = parent; parent = current;


            current = compare( item, current ) < 0 ?


                current.left : current.right;


            


            // Check if two red children; fix if so


            if( current.left.color == RED && current.right.color == RED )


                handleReorient( item );


        }


        


        // Insertion fails if already present


        if( current != nullNode )


            throw new DuplicateItemException( item.toString( ) );


        current = new RedBlackNode( item, nullNode, nullNode );


        


        // Attach to parent


        if( compare( item, parent ) < 0 )


            parent.left = current;


        else


            parent.right = current;


        handleReorient( item );


    }


    


    /**


     * Remove from the tree.


     * @param x the item to remove.


     * @throws UnsupportedOperationException if called.


     */


    public void remove( Comparable x ) {


        throw new UnsupportedOperationException( );


    }


    


    /**


     * Find the smallest item  the tree.


     * @return the smallest item or null if empty.


     */


    public Comparable findMin( ) {


        if( isEmpty( ) )


            return null;


        


        RedBlackNode itr = header.right;


        


        while( itr.left != nullNode )


            itr = itr.left;


        


        return itr.element;


    }


    


    /**


     * Find the largest item in the tree.


     * @return the largest item or null if empty.


     */


    public Comparable findMax( ) {


        if( isEmpty( ) )


            return null;


        


        RedBlackNode itr = header.right;


        


        while( itr.right != nullNode )


            itr = itr.right;


        


        return itr.element;


    }


    


    /**


     * Find an item in the tree.


     * @param x the item to search for.


     * @return the matching item or null if not found.


     */


    public Comparable find( Comparable x ) {


        nullNode.element = x;


        current = header.right;


        


        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( ) {


        header.right = nullNode;


    }


    


    /**


     * Print all items.


     */


    public void printTree( ) {


        printTree( header.right );


    }


    


    /**


     * Internal method to print a subtree in sorted order.


     * @param t the node that roots the tree.


     */


    private void printTree( RedBlackNode t ) {


        if( t != nullNode ) {


            printTree( t.left );


            System.out.println( t.element );


            printTree( t.right );


        }


    }


    


    /**


     * Test if the tree is logically empty.


     * @return true if empty, false otherwise.


     */


    public boolean isEmpty( ) {


        return header.right == nullNode;


    }


    


    /**


     * Internal routine that is called during an insertion


     * if a node has two red children. Performs flip and rotations.


     * @param item the item being inserted.


     */


    private void handleReorient( Comparable item ) {


        // Do the color flip


        current.color = RED;


        current.left.color = BLACK;


        current.right.color = BLACK;


        


        if( parent.color == RED )   // Have to rotate


        {


            grand.color = RED;


            if( ( compare( item, grand ) < 0 ) !=


                    ( compare( item, parent ) < 0 ) )


                parent = rotate( item, grand );  // Start dbl rotate


            current = rotate( item, great );


            current.color = BLACK;


        }


        header.right.color = BLACK; // Make root black


    }


    


    /**


     * Internal routine that performs a single or double rotation.


     * Because the result is attached to the parent, there are four cases.


     * Called by handleReorient.


     * @param item the item in handleReorient.


     * @param parent the parent of the root of the rotated subtree.


     * @return the root of the rotated subtree.


     */


    private RedBlackNode rotate( Comparable item, RedBlackNode parent ) {


        if( compare( item, parent ) < 0 )


            return parent.left = compare( item, parent.left ) < 0 ?


                rotateWithLeftChild( parent.left )  :  // LL


                rotateWithRightChild( parent.left ) ;  // LR


        else


            return parent.right = compare( item, parent.right ) < 0 ?


                rotateWithLeftChild( parent.right ) :  // RL


                rotateWithRightChild( parent.right );  // RR


    }


    


    /**


     * Rotate binary tree node with left child.


     */


    private static RedBlackNode rotateWithLeftChild( RedBlackNode k2 ) {


        RedBlackNode k1 = k2.left;


        k2.left = k1.right;


        k1.right = k2;


        return k1;


    }


    


    /**


     * Rotate binary tree node with right child.


     */


    private static RedBlackNode rotateWithRightChild( RedBlackNode k1 ) {


        RedBlackNode k2 = k1.right;


        k1.right = k2.left;


        k2.left = k1;


        return k2;


    }


    


    private static class RedBlackNode {


        // Constructors


        RedBlackNode( Comparable theElement ) {


            this( theElement, null, null );


        }


        


        RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {


            element  = theElement;


            left     = lt;


            right    = rt;


            color    = RedBlackTree.BLACK;


        }


        


        Comparable   element;    // The data in the node


        RedBlackNode left;       // Left child


        RedBlackNode right;      // Right child


        int          color;      // Color


    }


    


    private RedBlackNode header;


    private static RedBlackNode nullNode;


    static         // Static initializer for nullNode


    {


        nullNode = new RedBlackNode( null );


        nullNode.left = nullNode.right = nullNode;


    }


    


    private static final int BLACK = 1;    // Black must be 1


    private static final int RED   = 0;


    


    // Used in insert routine and its helpers


    private static RedBlackNode current;


    private static RedBlackNode parent;


    private static RedBlackNode grand;


    private static RedBlackNode great;


    


    


    // Test program


    public static void main( String [ ] args ) {


        RedBlackTree t = new RedBlackTree( );


        final int NUMS = 400000;


        final int GAP  =  35461;


        


        System.out.println( "Checking... (no more output means success)" );


        


        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )


            t.insert( new Integer( i ) );


        


        if( ((Integer)(t.findMin( ))).intValue( ) != 1 ||


                ((Integer)(t.findMax( ))).intValue( ) != NUMS - 1 )


            System.out.println( "FindMin or FindMax error!" );


        


        for( int i = 1; i < NUMS; i++ )


            if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )


                System.out.println( "Find error1!" );


    }


}








/**


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


    }


}

Javist

Красное дерево черный осуществления в Java

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