java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips arrow java.lang arrow Binary Search Tree Implementation in Java
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4093
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Binary Search Tree Implementation in Java E-mail
User Rating: / 498
PoorBest 

In computer science, a binary search tree (BST) is a binary tree which has the following properties:

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

The major advantage of binary search trees is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

Following code shows how to implement a binary search tree in 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 );
    }
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.