CSci 2101: Binary Search Tree

We added a recursive put method:


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

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

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

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

	/**
	 * 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 {
			putHelper(root, key, value);
		}
	}

	private void putHelper(BSTNode n, K key, V value) {

		if (key.compareTo(n.key) > 0) {
			if (n.right == null) {
				n.right = new BSTNode(key, value);
			} else {
				putHelper(n.right, key, value);
			}
		} else {
			if (n.left == null) {
				n.left = new BSTNode(key, value);
			} else {
				putHelper(n.left, key, value);
			}
		}
	}


	/**
	 * 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) {
		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) {
		return null;
	}
	
	/**
	 * Clears all elements from a given tree.
	 * The resulting tree is empty.
	 */
	public void clear() {
		
	}

	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;
		}

	}
}

CSci 2101 course web site.