Notes on Binary Search Trees (1/15/15)

Today I worked on Binary Search Trees.

Binary Search Trees, according to EIMACS, are binary trees whose values are instances of reference types - they implement the Comparable<T> interface. They can never have the same value more than once.

In a Binary Search Tree, each left value is less than the root value, and each right value is greater than the root value. A good picture example of this is this, also from EIMACS:

A perfect example as to why a developer would choose a Binary Search Tree is that it has a very efficient search algorithm, as seen below. This method will return a the TreeNode where the defined value exists, and otherwise, return null. As a result of the compareTo method and the Comparable interface, it is much quicker and efficient than other methods.

static TreeNode searchBST( TreeNode tree, Comparable value )
{
    if ( tree == null ){
        return null;

    }
    Object rootVal = tree.getValue();
    if ( value.equals( rootVal ) ){
        return tree;

    }
    if ( value.compareTo( rootVal ) < 0 ){
        return searchBST( tree.getLeft(), value );

    }
    else
}

As previously stated, this method has a great deal of use if you're working with trees. Granted that your Binary Tree is pre-sorted, this method will allow for fast accessing of data - a perfect reason to use a Binary Tree.

Creating Binary Search Trees isn't all too difficult, as shown in EIMACS, the buildBST and insertLeaf methods, as shown below, can both create and insert data into a Binary Search Tree.

public static TreeNode buildBST( ArrayList<Comparable> values )
{
    TreeNode newTree = null;
    for ( int i = 0 ; i < values.size() ; i++ ){
        newTree = insertLeaf( newTree, values.get( i ) ); 

    }
    return newTree;
}


public static TreeNode insertLeaf( TreeNode tree, Comparable value )
{
    if ( tree == null ){
        return new TreeNode( value );

    }

    if ( value.compareTo( tree.getValue() ) < 0 ){
        tree.setLeft( insertLeaf( tree.getLeft(), value ) );
    }
    else {
        tree.setRight( insertLeaf( tree.getRight(), value ) );
    }
    return tree;
}

Additionally noted in this section is the TreeSet<E> interface. All objects in this must be Comparable<E> objects. It also allows for quick searching, adding, and removing of objects, none of which take more than O(log(n)) time.

TreeMap<K, V> is also a noted interface. All objects in this must be Comparable<K> objects, and the methods available for this interface are get, put, containsKey, and remove. They also can be completed in O(log(n)) time or less, and objects in the TreeMap are stored and retrievable in the same order, which is advantageous in certain situations.

I also began to install Xcode, which apparently can be used for Java. I wanted to experiment with it a bit later on when I go back to Android development, and since I've heard it's a fairly decent IDE, I thought it would be worth a try. It only took two or so minutes, so I didn't lose too much time by doing this either!

Tomorrow I will add information on Heaps!