Blame | Last modification | View Log | RSS feed
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
NodeSerializer serializer;
// Constructor
public BSTree(MemManager mem) {
serializer = new NodeSerializer(mem);
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) {
CityRecord record = serializer.handleToCityRecord((Handle)root.getElement());
// If coordinates do not match, keep searching from the right child
// if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) {
if (record.getX() != x || record.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) {
serializer.removeCityRecordHandle((Handle)root.getElement());
return root.getRight();
} else if (root.getRight() == null) {
serializer.removeCityRecordHandle((Handle)root.getElement());
return root.getLeft();
} else {
serializer.removeCityRecordHandle((Handle)root.getElement());
// 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) {
serializer.removeCityRecordHandle((Handle)root.getElement());
return root.getRight();
} else if (root.getRight() == null) {
serializer.removeCityRecordHandle((Handle)root.getElement());
return root.getLeft();
} else {
serializer.removeCityRecordHandle((Handle)root.getElement());
// 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;
}
}
}