DictionaryBST

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 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
     */
    private Node removeMin(K key) {
        findMin(key);
    }

    /**
     * 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
     */
    private Node removeMax(K key) {
        findMax(key);
    }

    /**
     * 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
         */
        private 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;
        }
    }
}