Subversion Repositories Code-Repo

import java.util.ArrayList;

// Generic BST implementation

public class BSTree<K extends Comparable<? super K>, E> implements Dictionary<K, E> {

	private BSTreeNode<K,E> root;	// Root of the BST

	// Constructor

	public BSTree() {

		this.root = null;

	}

	// Inserts a node into the BST

	public void insert(K key, E element) {

		// Set the BST root as the returned node

		this.root = insertRecursive(root, key, element);

	}

	// Removes a node from the BST given the key

	public void remove(K key) {

		// Adds invalid coordinates if none are specified

		this.remove(key, -1, -1);

	}

	public void remove(K key, int x, int y) {

		// Check if node exists

		E temp = findRecursive(root, key);

		if (temp != null) {

			// Remove the node

			this.root = removeRecursive(root, key, x, y);

		}

	}

	// Returns a node from the BST given the key

	public E find(K key) {

		return findRecursive(root, key);

	}

	// Returns a list of all nodes with the given key

	public ArrayList<E> findAll(K key) {

		ArrayList<E> elementList = new ArrayList<E>();

		findAllRecursive(root, key, elementList);

		return elementList;

	}

	// Removes all nodes from the BST

	public void clear() {

		this.root = null;

	}

	// Recursively inserts a node into the BST

	private BSTreeNode<K,E> insertRecursive(BSTreeNode<K,E> root, K key, E element) {

		if (root == null)

			// If there are no nodes in the BST, create and return a new node

			return new BSTreeNode<K,E>(key, element);

		if (root.getKey().compareTo(key) > 0)

			// If passed key is smaller, insert into left child

			root.setLeft(insertRecursive(root.getLeft(), key, element));

		else

			// If passed key is greater, insert into right child

			root.setRight(insertRecursive(root.getRight(), key, element));

		return root;

	}

	// Recursively searches minimal nodes for matches to the given key

	private E findRecursive(BSTreeNode<K,E> root, K key) {

		if (root == null)

			return null;

		if (root.getKey().compareTo(key) > 0)

			// If passed key is smaller, search the left child

			return findRecursive(root.getLeft(), key);

		else if (root.getKey().compareTo(key) == 0)

			// If key is found, return with the found element

			return root.getElement();

		else

			// If key is not found, search the right child

			return findRecursive(root.getRight(), key);

	}

	// Recursively searches all nodes for matches to the given key

	private void findAllRecursive(BSTreeNode<K,E> root, K key, ArrayList<E> elementList) {

		if (root == null)

			return;

		// If key matches, save to list

		if (root.getKey().compareTo(key) == 0)

			elementList.add(root.getElement());

		// Recursively call search on all possible nodes

		if (root.getKey().compareTo(key) > 0)

			findAllRecursive(root.getLeft(), key, elementList);

		else

			findAllRecursive(root.getRight(), key, elementList);

	}

	// Recursively removes a node from the BST given a key

	private BSTreeNode<K,E> removeRecursive(BSTreeNode<K,E> root, K key, int x, int y) {

		if (root == null)

			return null;

		// Find the node to remove

		if (root.getKey().compareTo(key) > 0)

			root.setLeft(removeRecursive(root.getLeft(), key, x, y));

		else if (root.getKey().compareTo(key) < 0)

			root.setRight(removeRecursive(root.getRight(), key, x, y));

		// Node's key matches

		else {

			// If we want to narrow it down by coordinates as well

			if (x >= 0 && y >= 0) {

				// If coordinates do not match, keep searching from the right child

				if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) {

					root.setRight(removeRecursive(root.getRight(), key, x, y));

				} else {

					// If one of the leaves is null, just return the other leaf

					if (root.getLeft() == null)

						return root.getRight();

					else if (root.getRight() == null)

						return root.getLeft();

					else {

						// Otherwise create a new node with the smallest value on the right leaf

						BSTreeNode<K,E> temp = getMin(root.getRight());

						root.setElement(temp.getElement());

						root.setKey(temp.getKey());

						root.setRight(deleteMin(root.getRight()));

					}

				}

			// Otherwise just remove the node

			} else {

				// If one of the leaves is null, just return the other leaf

				if (root.getLeft() == null)

					return root.getRight();

				else if (root.getRight() == null)

					return root.getLeft();

				else {

					// Otherwise create a new node with the smallest value on the right leaf

					BSTreeNode<K,E> temp = getMin(root.getRight());

					root.setElement(temp.getElement());

					root.setKey(temp.getKey());

					root.setRight(deleteMin(root.getRight()));

				}

			}

		}

		return root;

	}

	// Recursively returns the minimum key node

	private BSTreeNode<K,E> getMin(BSTreeNode<K,E> root) {

		if (root.getLeft() == null)

			return root;

		else

			return getMin(root.getLeft());

	}

	// Recursively deletes the minimum key node

	private BSTreeNode<K,E> deleteMin(BSTreeNode<K,E> root) {

		if (root.getLeft() == null)

			return root.getRight();

		else {

			root.setLeft(deleteMin(root.getLeft()));

			return root;

		}

	}

}