CSci 2101: Binary Search Tree

This is a solution from the group that worked in Sci 2185. Removing an element is not finished at this point.

JUnit Test code for Binary Search Tree


import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class TestBST {
    private BinarySearchTree<Integer,String> emptyTree = new BinarySearchTree<Integer,String>();
    private BinarySearchTree<Integer,String> eightNodesTree= new BinarySearchTree<Integer,String>();
   
    @Before
    public void setUp() {
        eightNodesTree.put(4,"apple");
        eightNodesTree.put(6,"banana");
        eightNodesTree.put(1,"strawberry");
        eightNodesTree.put(3,"kiwi");
        eightNodesTree.put(7,"lemon");
        eightNodesTree.put(10,"lime");
        eightNodesTree.put(6,"mango");
        eightNodesTree.put(8,"pear");
    }
   
    @Test
    public void TestEmpty() {
        assertTrue(emptyTree.isEmpty());
        assertEquals(0,emptyTree.size());
    }
   
    @Test
    public void TestNonEmpty() {
        emptyTree.put(4,"apple");
        assertFalse(emptyTree.isEmpty());
        assertEquals(1,emptyTree.size());
    }
   
    @Test
    public void TestPutGetRoot() {
        emptyTree.put(4,"apple");
        assertEquals("apple",emptyTree.get(4));
    }
   
    @Test
    public void TestGetFromEmpty() {
        assertNull(emptyTree.get(4));
    }   
   
    @Test
    public void TestGet() {
        assertEquals("strawberry",eightNodesTree.get(1));
        assertEquals("lemon",eightNodesTree.get(7));
    }   
   
    @Test
    public void TestGetNotThere() {
        assertNull(eightNodesTree.get(5));
    }   
   
    @Test (expected=NullPointerException.class)
    public void TestNullKey() {
        assertNull(eightNodesTree.get(null));
    }
   
    @Test
    public void TestSize() {
        assertEquals(8,eightNodesTree.size());
    }
   
    @Test
    public void TestClear() {
        eightNodesTree.clear();
        assertTrue(eightNodesTree.isEmpty());
        assertEquals(0,eightNodesTree.size());
        assertNull(eightNodesTree.get(4));
    }   
   
    // to-do: tests for remove, tree traversals
    @Test
    public void TestRemove() {
        assertEquals("pear", eightNodesTree.remove(8));
        assertEquals(7,eightNodesTree.size());
    }

    @Test 
    public void TestInOrder() {
    	List<Pair<Integer,Integer>> thelist = new ArrayList<Pair<Integer,Integer>>();
    	thelist.add(new Pair<Integer,Integer>(1,1));
    	thelist.add(new Pair<Integer,Integer>(2,2));
    	thelist.add(new Pair<Integer,Integer>(3,3));
    	thelist.add(new Pair<Integer,Integer>(4,4));
    	assertEquals(thelist,fourNodesTree.inOrder());
    
    }
    
    @Test 
    public void TestEmptyInOrder() {
    	List<Pair<Integer,Integer>> thelist = new ArrayList<Pair<Integer,Integer>>();
    	assertEquals(thelist,emptyTree.inOrder());
    }
}

Starting code for binary serach tree:



/**
 * Binary search tree stores values indexed by keys. Keys must be Comparable and
 * are organized based on their natural ordering (i.e. the ordering given by
 * their compareTo). Values can be of any object type. This tree implementation
 * is not balanced, i.e. it may behave as a linked list in the worst case. Keys
 * may be repeated. Somewhat modeled after Map<K,V> classes in the Java
 * Collections Framework
 *
 * Author: Elena Machkasova For UMM CSci 2101 class (version for Summer 2011).
 **/

public class BinarySearchTree<K extends Comparable<K>, V> {
    private BSTNode root = null;
    private int count=0;

    /**
     * @return true if the tree is empty, false otherwise
     **/
    public boolean isEmpty() {
        return (root == null);
       
    }

    /**
     * @return the number of elements in the tree
     **/
    public int size() {
        return count;
    }

    /**
     * Adds a given value indexed with a given key to the tree according to the
     * binary search structure
     *
     * @param key
     *            - the key of the given element
     * @param value
     *            - the value of the given element
     */
    public void put(K key, V value) {
        if (root == null){
            root= new BSTNode(key,value);
        }
        else{
            moveDown(root, new BSTNode(key, value));
        }
        count++;
    }
    private void moveDown(BSTNode current, BSTNode element){
        if (current.key.compareTo(element.key) <= 0) {
            // go right
            if (current.right != null) {
                moveDown(current.right, element);
            }
            else {
                current.right = element;
            }
        }
        else {
            // go left
            if (current.left != null) {
                moveDown(current.left, element);
            }
            else {
                current.left = element;
            }
        }
    }

    /**
     * returns a value associated with the given key in this binary search tree.
     * If multiple values are associated with this key, any one may be returned.
     * If there is no element associated with this key, null is returned.
     *
     * @param key
     *            - the key to search for.
     * @return - a value to which the specified key is mapped, or null if this
     *         tree contains no mapping for the key
     * @throws NullPointerException if the key is null       
     */
    public V get(K key) {
        if (key == null){
            throw new NullPointerException();
        }
        BSTNode current = root;
        while (current != null){
            if (current.key.compareTo(key) == 0) {
                return current.value;
            }
            else if (current.key.compareTo(key) < 0) {
                // go right
                current = current.right;
            }
            else {
                // go left
                current = current.left;
            }
        }       
        return null;   
    }

    /**
     * Removes an element with the given key. The resulting tree is a binary
     * search tree. If there is no such key, the tree is unchanged. If there are
     * multiple values associated with this key, only one is removed. Returns
     * the value associated with this key or null if there is no such value.
     *
     * @param key
     *            - the key
     * @return - a value to which the specified key is mapped, or null if this
     *         tree contains no mapping for the key
     * @throws NullPointerException if the key is null        
     */
    public V remove(K key) {
        if (key == null){
            throw new NullPointerException();
        }
        BSTNode current = root;
       
        while (current != null){
            if (current.key.compareTo(key) == 0) {
                return removeNode(current);
            }
            else if (current.left.key.compareTo(key) == 0){
                return removeNode(current.left);
            }
            else if(current.right.key.compareTo(key) == 0) {
                return removeNode(current.right);
            }
            else if (current.key.compareTo(key) < 0) {
                // go right
                current = current.right;
            }
            else {
                // go left
                current = current.left;
            }
        }       
        return null;
    }
// method assumes not removing root
    private V removeNode(BSTNode parent, boolean left) {
        BSTNode nodeToRemove = left ? parent.left : parent.right;
        V item = nodeToRemove.value;
       
        if (nodeToRemove.right != null) {
            if (left) {
                parent.left = nodeToRemove.right;
            }
            else {
                parent.right = nodeToRemove.right;
            }
            // working here - go to bottom right
        }
        else {
            if (left) {
                parent.left = nodeToRemove.left;
            }
            else {
                parent.right = nodeToRemove.left;
            }
            // working here - go to bottom left
        }
       
        return item;
    }
    /**
     * Clears all elements from a given tree.
     * The resulting tree is empty.
     */
    public void clear() {
        root = null;
        count = 0;
    }

    private class BSTNode {
        public K key;
        public V value;
        public BSTNode left = null;
        public BSTNode right = null;

        // null key will generate a null pointer exception when
        // a method (such as compareTo) is called on it.
        // This is fine, according to the JCF specification.
        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
	public ArrayList<Pair<K,V>> inOrder() {
		ArrayList<Pair<K,V>> arrList= new ArrayList<Pair<K,V>>();
		inOrderIt(root, arrList);
		return arrList;
	}
	
	private void inOrderIt(BSTNode node, ArrayList<Pair<K,V>> aList){
		if (node == null) return;
		inOrderIt(node.left, aList);
		aList.add(new Pair<K,V>(node.key, node.value));
		inOrderIt(node.right, aList);
	}
}

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.