Бинарных деревьев осуществления поиска в Java

В компьютерной науке, бинарных деревьев поиска (BST) является бинарным деревом, которое обладает следующими свойствами:

  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than or equal to the node’s value.
  • The right subtree of a node contains only values greater than or equal to the node’s value.

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

Двоичные деревья поиска основные структуры данных, используемые для построения более абстрактных структур данных, таких как наборы, мультимножеств и ассоциативные массивы.

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


// BinarySearchTree class

//

// CONSTRUCTION: with no initializer

//

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

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

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

// void removeMin( )      --> Remove minimum item

// 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, remove, and removeMin if warranted



/**

 * Implements an unbalanced binary search tree.

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

 @author Mark Allen Weiss

 */

public class BinarySearchTree {

    /**

     * Construct the tree.

     */

    public BinarySearchTree( ) {

        root = null;

    }

    

    /**

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

        root = removex, root );

    }

    

    /**

     * Remove minimum item from the tree.

     @throws ItemNotFoundException if tree is empty.

     */

    public void removeMin( ) {

        root = removeMinroot );

    }

    

    /**

     * Find the smallest item in the tree.

     @return smallest item or null if empty.

     */

    public Comparable findMin( ) {

        return elementAtfindMinroot ) );

    }

    

    /**

     * Find the largest item in the tree.

     @return the largest item or null if empty.

     */

    public Comparable findMax( ) {

        return elementAtfindMaxroot ) );

    }

    

    /**

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

        return elementAtfindx, root ) );

    }

    

    /**

     * Make the tree logically empty.

     */

    public void makeEmpty( ) {

        root = null;

    }

    

    /**

     * Test if the tree is logically empty.

     @return true if empty, false otherwise.

     */

    public boolean isEmpty( ) {

        return root == null;

    }

    

    /**

     * Internal method to get element field.

     @param t the node.

     @return the element field or null if t is null.

     */

    private Comparable elementAtBinaryNode t ) {

        return t == null null : t.element;

    }

    

    /**

     * 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.

     */

    protected BinaryNode insertComparable x, BinaryNode t ) {

        ift == null )

            t = new BinaryNode);

        else ifx.compareTot.element )

            t.left = insertx, t.left );

        else ifx.compareTot.element )

            t.right = insertx, t.right );

        else

            throw new DuplicateItemExceptionx.toString( ) );  // Duplicate

        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.

     */

    protected BinaryNode removeComparable x, BinaryNode t ) {

        ift == null )

            throw new ItemNotFoundExceptionx.toString( ) );

        ifx.compareTot.element )

            t.left = removex, t.left );

        else ifx.compareTot.element )

            t.right = removex, t.right );

        else ift.left != null && t.right != null // Two children

        {

            t.element = findMint.right ).element;

            t.right = removeMint.right );

        else

            t = t.left != null ? t.left : t.right;

        return t;

    }

    

    /**

     * Internal method to remove minimum item from a subtree.

     @param t the node that roots the tree.

     @return the new root.

     @throws ItemNotFoundException if x is not found.

     */

    protected BinaryNode removeMinBinaryNode t ) {

        ift == null )

            throw new ItemNotFoundException( );

        else ift.left != null ) {

            t.left = removeMint.left );

            return t;

        else

            return t.right;

    }

    

    /**

     * Internal method to find the smallest item in a subtree.

     @param t the node that roots the tree.

     @return node containing the smallest item.

     */

    protected BinaryNode findMinBinaryNode t ) {

        ift != null )

            whilet.left != null )

                t = t.left;

        

        return t;

    }

    

    /**

     * Internal method to find the largest item in a subtree.

     @param t the node that roots the tree.

     @return node containing the largest item.

     */

    private BinaryNode findMaxBinaryNode t ) {

        ift != null )

            whilet.right != null )

                t = t.right;

        

        return t;

    }

    

    /**

     * Internal method to find an item in a subtree.

     @param x is item to search for.

     @param t the node that roots the tree.

     @return node containing the matched item.

     */

    private BinaryNode findComparable x, BinaryNode t ) {

        whilet != null ) {

            ifx.compareTot.element )

                t = t.left;

            else ifx.compareTot.element )

                t = t.right;

            else

                return t;    // Match

        }

        

        return null;         // Not found

    }

    

    /** The tree root. */

    protected BinaryNode root;

    

    

    // Test program

    public static void mainString [ ] args ) {

        BinarySearchTree t = new BinarySearchTree( );

        final int NUMS = 4000;

        final int GAP  =   37;

        

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

        

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

            t.insertnew Integer) );

        

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

            t.removenew Integer) );

        

        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"Find error1!" );

        

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

            ift.findnew Integer) ) != null )

                System.out.println"Find error2!" );

        }

    }

}





// Basic node stored in unbalanced binary search trees

// Note that this class is not accessible outside

// of this package.



class BinaryNode {

    // Constructors

    BinaryNodeComparable theElement ) {

        element = theElement;

        left = right = null;

    }

    

    // Friendly data; accessible by other package routines

    Comparable element;      // The data in the node

    BinaryNode left;         // Left child

    BinaryNode right;        // Right child

}





/**

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