Untitled

package dataStructures.trees;

import java.util.*;

/**
 * A binary tree of TreeNodes, which contain words in a document.
 *
 * @author Y3761870
 * @version 29/Apr/2009
 */
public class BinaryTree implements Tree
{
        /**
         * The root node of the tree.
         */
    protected TreeNode root = null;

    /**
     * Inserts a new word into the tree or updates the record for an existing word with additional locations.
     *
     * @param data A string containing the data item to be inserted into the Tree
     * @param lineNo The line number the data item appears in the document
     * @param index The offset along the line that the word appears
     */
    public void insert(String data, int lineNo, int index)
    {
                // if we don't have a root node, create one
        if (root == null)
            root = new TreeNode(data, new WordLocation(lineNo, index));

        else
                        // replace the node with a node containing a subtree with the new node in it
            root = insert(root, data, new WordLocation(lineNo, index));
    }

        /**
         * Returns a modified subtree with the word inserted or the word's node modified to reflect the new location
         *
         * @param subtree The subtree to be modified
         * @param data The word to be inserted
         * @param location the location of the word
         */
    protected TreeNode insert(TreeNode subtree, String data, WordLocation location)
    {
                // no need to duplicate the comparison, so store the results
        int comparison = subtree.getData().compareTo(data);

                // element > data
        if (comparison > 0)
        {
                        // if there's no left child
            if (subtree.getLeftChild() == null)
                                // add a new one
                subtree.addLeftChild(new TreeNode(data, location));

                        // there is a left child
            else
                                // so delegate the insertion to the left child
                subtree.addLeftChild(insert(subtree.getLeftChild(), data, location));
        }

                // element < data
        else if (comparison < 0)
        {
            if (subtree.getRightChild() == null)
                subtree.addRightChild(new TreeNode(data, location));

            else
                subtree.addRightChild(insert(subtree.getRightChild(), data, location));
        }

                // element == data
        else
                        // duplicate, so add the new location
            subtree.addLocation(location);

                // return modified subtree
        return subtree;
    }

    /**
     * Remove node with the given data
     *
     * @param data A String containing the data item to be removed from the Tree
     */
    public void remove(String data)
    {
                // no need to do anything if there's no root node
        if (root != null)
                        // change root to a modified version of the root tree with the relevant data removed
            root = remove(root, data);
    }

        /**
         * Gives a modified version of the given node's tree with the relevant data removed (if it exists)
         *
         * @param subtree The subtree to modify
         * @param data The data to remove
         */
    protected TreeNode remove(TreeNode subtree, String data)
    {
        int comparison = subtree.getData().compareTo(data);

                // element > data
        if (comparison > 0)
                        // delegate the removal to the left subtree
            subtree.addLeftChild(remove(subtree.getLeftChild(), data));

                // element < data
        else if (comparison < 0)
            subtree.addRightChild(remove(subtree.getRightChild(), data));

                // element == data
                // delete this node!
        else
        {
                        // if there's no left child
            if (subtree.getLeftChild() == null)
                                // then the node is just the right child (this has the effect of making the current node null if the right node is null)
                subtree = subtree.getRightChild();

                        // but if there is a left child
            else
            {
                                // if there is no right child
                if (subtree.getRightChild() == null)
                                        // replace the node with its left subtree
                    subtree = subtree.getLeftChild();

                // tree has at least two branches
                else
                {
                                        // find the successor (the minimum of the right branch of the node)
                    TreeNode successor = getMinimum(subtree.getRightChild());

                                        // remove the original successor, which is now a duplicate
                                        subtree.addRightChild(remove(subtree.getRightChild(), successor.getData()));

                                        // give the successor the children of the current node
                                        successor.addLeftChild(subtree.getLeftChild());
                                        successor.addRightChild(subtree.getRightChild());

                                        // then make the current node the successor
                                        subtree = successor;
                }
            }
        }

        return subtree;
    }

        /**
         * Gets the minimum node (smallest value) from the given subtree.
         *
         * @param node A subtree
         */
    protected TreeNode getMinimum(TreeNode node)
    {
                // if there are more left children
        if (node.getLeftChild() != null)
                        // this is not left-most (minimum) element, progress further down the tree
            return getMinimum(node.getLeftChild());

                // this is the left-most element, return it.
        return node;
    }

    /**
     * Searches for the given word. The ArrayList of WordLocation objects has the location of all occurences of the word in the original document.
         *
     * @param data The word we are looking for
     * @return ArrayList containing all occurences of the word in the document and where each occurance is located
     */
    public ArrayList<WordLocation> find(String data)
    {
                // if the tree is empty
        if (isEmpty())
                        // return an empty list
            return new ArrayList<WordLocation>();

                // otherwise delegate the finding to the first subtree (from the root)
        return find(root, data);
    }

        /**
         * Searches for the given word in the subtree specified.
         *
         * @param node The subtree to search
         * @param data The word we are looking for
         * @return An ArrayList of all occurences of the word
         */
    protected ArrayList<WordLocation> find(TreeNode node, String data)
    {
        int comparison = node.getData().compareTo(data);

                // element > data
        if (comparison > 0)
        {
                        // if we've gotten to the end of the tree
            if (node.getLeftChild() == null)
                                // just return an empty list
                return new ArrayList<WordLocation>();

            else
                                // otherwise, delegate to searching the next subtree
                return find(node.getLeftChild(), data);
        }

                // element < data
        else if (comparison < 0)
        {
            if (node.getRightChild() == null)
                return new ArrayList<WordLocation>();

            else
                return find(node.getRightChild(), data);
        }

                // element == data
        else
                        // return the list of locations at this node
            return node.getLocations();
    }

    /**
     * Checks if a tree is empty
         *
     * @return true if tree is empty
     */
    public boolean isEmpty()
    {
        return (root == null);
    }

    /**
     * Remove all nodes from the tree (destructive).
     */
    public void makeEmpty()
    {
        root = null;
    }

    /**
     * Provides the root node of the tree (non-destructive)
         *
     * @return TreeNode The node of the Tree
     */
    public TreeNode getRootNode()
    {
        return root;
    }
}