0,0 → 1,161 |
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; |
} |
} |
} |