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.

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.