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