Красное дерево черный осуществления в 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 RedBlackNodenull );

        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 compareComparable item, RedBlackNode t ) {

        ift == header )

            return 1;

        else

            return item.compareTot.element );

    }

    

    /**

     * Insert into the tree.

     @param item the item to insert.

     @throws DuplicateItemException if item is already present.

     */

    public void insertComparable item ) {

        current = parent = grand = header;

        nullNode.element = item;

        

        whilecompareitem, current != ) {

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

            current = compareitem, current ?

                current.left : current.right;

            

            // Check if two red children; fix if so

            ifcurrent.left.color == RED && current.right.color == RED )

                handleReorientitem );

        }

        

        // Insertion fails if already present

        ifcurrent != nullNode )

            throw new DuplicateItemExceptionitem.toString( ) );

        current = new RedBlackNodeitem, nullNode, nullNode );

        

        // Attach to parent

        ifcompareitem, parent )

            parent.left = current;

        else

            parent.right = current;

        handleReorientitem );

    }

    

    /**

     * Remove from the tree.

     @param x the item to remove.

     @throws UnsupportedOperationException if called.

     */

    public void removeComparable x ) {

        throw new UnsupportedOperationException( );

    }

    

    /**

     * Find the smallest item  the tree.

     @return the smallest item or null if empty.

     */

    public Comparable findMin( ) {

        ifisEmpty( ) )

            return null;

        

        RedBlackNode itr = header.right;

        

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

        ifisEmpty( ) )

            return null;

        

        RedBlackNode itr = header.right;

        

        whileitr.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 findComparable x ) {

        nullNode.element = x;

        current = header.right;

        

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

        header.right = nullNode;

    }

    

    /**

     * Print all items.

     */

    public void printTree( ) {

        printTreeheader.right );

    }

    

    /**

     * Internal method to print a subtree in sorted order.

     @param t the node that roots the tree.

     */

    private void printTreeRedBlackNode t ) {

        ift != nullNode ) {

            printTreet.left );

            System.out.printlnt.element );

            printTreet.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 handleReorientComparable item ) {

        // Do the color flip

        current.color = RED;

        current.left.color = BLACK;

        current.right.color = BLACK;

        

        ifparent.color == RED )   // Have to rotate

        {

            grand.color = RED;

            if( ( compareitem, grand !=

                    compareitem, parent ) )

                parent = rotateitem, grand );  // Start dbl rotate

            current = rotateitem, 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 rotateComparable item, RedBlackNode parent ) {

        ifcompareitem, parent )

            return parent.left = compareitem, parent.left ?

                rotateWithLeftChildparent.left )  :  // LL

                rotateWithRightChildparent.left ;  // LR

        else

            return parent.right = compareitem, parent.right ?

                rotateWithLeftChildparent.right :  // RL

                rotateWithRightChildparent.right );  // RR

    }

    

    /**

     * Rotate binary tree node with left child.

     */

    private static RedBlackNode rotateWithLeftChildRedBlackNode k2 ) {

        RedBlackNode k1 = k2.left;

        k2.left = k1.right;

        k1.right = k2;

        return k1;

    }

    

    /**

     * Rotate binary tree node with right child.

     */

    private static RedBlackNode rotateWithRightChildRedBlackNode k1 ) {

        RedBlackNode k2 = k1.right;

        k1.right = k2.left;

        k2.left = k1;

        return k2;

    }

    

    private static class RedBlackNode {

        // Constructors

        RedBlackNodeComparable theElement ) {

            thistheElement, null, null );

        }

        

        RedBlackNodeComparable 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 RedBlackNodenull );

        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 mainString [ ] args ) {

        RedBlackTree t = new RedBlackTree( );

        final int NUMS = 400000;

        final int GAP  =  35461;

        

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

        

        forint i = GAP; i != 0; i = i + GAP % NUMS )

            t.insertnew Integer) );

        

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

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

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

        

        forint i = 1; i < NUMS; i++ )

            if( ((Integer)(t.findnew Integer) ))).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 DuplicateItemExceptionString 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>