Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package binarysearchtreestuderende;
- public class DictionaryBST<K extends Comparable<K>, V> implements Dictionary<K, V> {
- private Node root;
- /**
- * Constructs an empty tree.
- */
- public DictionaryBST() {
- root = null;
- }
- @Override
- public V get(K key) {
- return find(key).value;
- }
- /**
- * Tries to find an object in the tree.
- *
- * @param obj the object to find
- * @return true if the object is contained in the tree
- */
- public Node find(K key) {
- Node current = root;
- boolean found = false;
- while (!found && current != null) {
- int d = current.key.compareTo(key);
- if (d == 0) {
- found = true;
- } else if (d > 0) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
- if (found) {
- return current;
- } else {
- return null;
- }
- }
- /**
- * Tries to find the smallest object in the tree.
- *
- * @param obj the object to find
- * @return true if the object is contained in the tree
- */
- public K findMin(K key) {
- Node parent = null;
- Node child = root;
- K toReturn = null;
- if (root.left == null) {
- if (root != null) {
- root = root.right;
- } else {
- while (child.left != null) {
- parent = child;
- child = parent.left;
- }
- }
- toReturn = child.data;
- parent.left = parent.left.right;
- }
- return toReturn;
- }
- /**
- * Tries to find the largest object in the tree.
- *
- * @param obj the object to find
- * @return true if the object is contained in the tree
- */
- public K findMax(K key) {
- Node max = root;
- if (root != null) {
- while (max.right != null) {
- max = max.right;
- }
- } else {
- return null;
- }
- return max.data;
- }
- /**
- * Inserts a new node into the tree.
- *
- * @param obj the object to insert
- */
- public void add(Comparable<K> obj) {
- Node newNode = new Node(null, null);
- newNode.left = null;
- newNode.right = null;
- if (root == null) {
- root = newNode;
- } else {
- root.addNode(newNode);
- }
- }
- @Override
- public boolean isEmpty() {
- boolean empty = true;
- if (root == null) {
- return empty;
- } else {
- return empty = false;
- }
- }
- @Override
- public V put(K key, V value) {
- Node newNode = new Node(key, value);
- if (root == null) {
- root = newNode;
- }
- return find(key).value;
- }
- /**
- * Tries to remove an object from the tree. Does nothing if the object is not
- * contained in the tree.
- *
- * @param obj the object to remove
- */
- @Override
- public V remove(K key) {
- Node toBeRemoved = root;
- Node parent = null;
- V toReturn = null;
- boolean found = false;
- while (!found && toBeRemoved != null) {
- int d = toBeRemoved.key.compareTo(key);
- if (d == 0) {
- found = true;
- toReturn = toBeRemoved.value;
- } else {
- parent = toBeRemoved;
- if (d > 0) {
- toBeRemoved = toBeRemoved.left;
- } else {
- toBeRemoved = toBeRemoved.right;
- }
- }
- }
- if (found) {
- // toBeRemoved contains obj
- // If one of the children is empty, use the other
- if (toBeRemoved.left == null || toBeRemoved.right == null) {
- Node newChild;
- if (toBeRemoved.left == null) {
- newChild = toBeRemoved.right;
- } else {
- newChild = toBeRemoved.left;
- }
- if (parent == null) // Found in root
- {
- root = newChild;
- } else if (parent.left == toBeRemoved) {
- parent.left = newChild;
- } else {
- parent.right = newChild;
- }
- } else {
- // Neither subtree is empty
- // Find smallest element of the right subtree
- Node smallestParent = toBeRemoved;
- Node smallest = toBeRemoved.right;
- while (smallest.left != null) {
- smallestParent = smallest;
- smallest = smallest.left;
- }
- // smallest contains smallest child in right subtree
- // Move contents, unlink child
- toBeRemoved.key = smallest.key;
- toBeRemoved.value = smallest.value;
- if (smallestParent == toBeRemoved) {
- smallestParent.right = smallest.right;
- } else {
- smallestParent.left = smallest.right;
- }
- }
- }
- return toReturn;
- }
- /**
- * Tries to remove the smallest object from the tree. Does nothing if the object
- * is not contained in the tree.
- *
- * @param obj the object to remove
- */
- @SuppressWarnings("unused")
- private Node removeMin(K key) {
- findMin(key);
- return null;
- }
- /**
- * Tries to remove the largest object from the tree. Does nothing if the object
- * is not contained in the tree.
- *
- * @param obj the object to remove
- */
- @SuppressWarnings("unused")
- private Node removeMax(K key) {
- findMax(key);
- return null;
- }
- /**
- * Prints the contents of the tree in sorted order.
- */
- public void print() {
- print(root);
- System.out.println();
- }
- /**
- * Prints a node and all of its descendants in sorted order.
- *
- * @param parent the root of the subtree to print
- */
- private void print(Node parent) {
- if (parent != null) {
- print(parent.left);
- System.out.print(parent.data + " ");
- print(parent.right);
- }
- }
- @Override
- public int size() {
- return size(root);
- }
- private int size(Node n) {
- if (n == null) {
- return 0;
- } else {
- return size(n.left) + size(n.right) + 1;
- }
- }
- /**
- * A node of a tree stores a data item and references to the left and right
- * child nodes.
- */
- private class Node {
- K key;
- V value;
- K data;
- Node left;
- Node right;
- public Node(K key, V value) {
- this.key = key;
- this.value = value;
- this.data = null;
- this.left = null;
- this.right = null;
- }
- /**
- * Inserts a new node as a descendant of this node.
- *
- * @param newNode the node to insert
- */
- public V addNode(Node newNode) {
- int comp = newNode.data.compareTo(data);
- V toReturn = null;
- if (comp < 0) {
- if (left == null) {
- left = newNode;
- } else {
- left.addNode(newNode);
- }
- } else if (comp > 0) {
- if (right == null) {
- right = newNode;
- } else {
- toReturn = value;
- value = newNode.value;
- }
- }
- return toReturn;
- }
- }
- }
Add Comment
Please, Sign In to add comment