Title: MyTreeSet
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

MyTreeSet Class

The TreeSet data structure has 2 very important features:

- Fast lookup
- When you iterate through the contents, the data comes out sorted
- Imagine you had the data shown below and you are trying to lookup: "gamma", "amber", "benefit"

Balanced MyTreeSet

Number of Expected Comparisons

- If your data structure is balanced, the following table gives you an idea of how many comparisons you might expect for a given Collection size.

- We are going to create a simplified data structure called MyTreeSet which will have some of the characteristics of TreeSet
- To make it work, we will need to create a Node data structure similar to what we did for the MyLinkedList data structure. It will look something like the drawing below:
- The left hand subtree for any given Node will contain all of the items less than the given node. The right hand subtree for any give Node will contain all of the items greater than the given node.

- Our MyTreeSet will work best when the items come in random order. No effort will be made to keep the tree balanced. We would expect that a proper implementation of TreeSet would have logic to balance the tree to some extent no matter what happens.
- So for example, the following tree will result from the following list of words: "omega", "alpha", "zeta", "epsilon", "gamma", "pi"
- This is not as balanced as it could be but no big problem yet

- Take a look at the data structure that results if we then receive the following words: "abe", "aardvark", "ben", "bee", "ambivalence", "ambition" , "amber", "amazon".
- This is beginning to look very unbalanced
- To fix this requires more complexity than we want to consider here. A good algorithm, would need to morph the following data structure into the balanced version you see at the beginning of these notes.
- We begin to have a trade off between how much work to put into reorganizing our data structure when it gets modified and how often are we going to be doing look ups that would benifit from a more balanced tree.
- So our code will do nothing just to keep the algorithms as simple as possible for this course.

MyTreeSet.java


import java.util.Iterator;
import java.util.LinkedList;

class Node<T>
{
    T value;
    Node<T> right;
    Node<T> left;
    Node<T> parent;

    Node(T value)
    {
        this.value = value;
        right = left= parent = null;
    }
}

public class MyTreeSet<T extends Comparable<T> > {
    private Node<T> root = null;
    private int treeSize = 0;

    public int size()
    {
        return treeSize;
    }

    public boolean add(T value)
    {
        Node<T> next = root;
        Node<T> parent = null;
        int diff;

        // Look to see if the Item is already in the Tree
        while(next != null)
        {
            parent = next;
            diff = value.compareTo(next.value);
            if (diff == 0) // found match and can't add ... must be unique
                return false;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }

        // Couldn't be found ... need to insert it.
        Node<T> newNode = new Node<T>(value);
        treeSize += 1;

        if (parent == null)
            root = newNode; // Must be the first Node
        else
        {
            // Create the parent, left/right links

            newNode.parent = parent;
            diff = value.compareTo(parent.value);
            if (diff > 0)
                parent.right = newNode;
            else
                parent.left = newNode;
        }

        return true;
    }

    public boolean contains(T value)
    {
        Node<T> next = root;
        int diff;

        while(next != null)
        {
            diff = value.compareTo(next.value);
            if (diff == 0) // found match
                return true;
            else if (diff > 0 )
                next = next.right;
            else
                next = next.left;
        }
        return false;
    }

    public Iterator<T> iterator()
    {
        return new MyIterator();
    }

    /******* Inner class Iterator *****/
    class MyIterator implements Iterator<T>
    {
        private Node<T> nextNode = null;

        MyIterator()
        {
            // Get the first node in the list
            nextNode = root;
            if (nextNode != null)
                goDownLeftLinks();
        }

        private void goDownLeftLinks()
        {
            while (nextNode.left != null)
                nextNode = nextNode.left;
        }
        private void moveToNext()
        {
            if (nextNode == null) return; // must be done
            if (nextNode.right != null)
            {
                // Need to follow the tree on the right
                nextNode = nextNode.right;
                goDownLeftLinks();
            }
            else
            {
                // We have already processed the left subtree, and there is no right tree.
                // We want to move up to find a parent where our nextNode is the left child
                // of the parent.  Note that nextNode has to be either a left or a right child.
                // So we keep climbing as long as nextNode is a right child.

                Node<T> parent = nextNode.parent;
                while (parent != null && nextNode == parent.right)
                {
                    nextNode = parent;
                    parent = nextNode.parent;
                }
                // if nextNode is null, then we are done.
                nextNode = parent;
            }
        }


        @Override
        public boolean hasNext() {
            if (nextNode== null)
                return false;
            return true;
        }

        @Override
        public T next() {
            T value = nextNode.value;
            moveToNext();
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Iterator.remove not implemented");

        }

    }
    // ******************  End of Inner class for Iterator

}



DemoMyTreeSet.java


import java.util.Iterator;

public class DemoMyTreeSet {

    public static void main(String[] args)
    {
        MyTreeSet<String> myTree = new MyTreeSet<String>();

        String[] arr = {"omega", "alpha", "zeta", "epsilon", "gamma", "pi",
                "abe", "aardvark", "ben", "bee", "ambivalence", "ambition" ,  "amber", "amazon"};

        for (int i=0; i < arr.length; i++)
            myTree.add(arr[i]);

        for (int i=0; i < arr.length; i++)
        {
            String s = arr[i];
            if (myTree.contains(s))
                System.out.println(s +" is IN the SET");
            else
                System.out.println(s +" is NOT in the SET");
        }

        Iterator<String> iter = myTree.iterator();
        while (iter.hasNext())
        {
            System.out.println("Iter: " + iter.next());
        }

    }

}



Tough Things Undone

- Keeping the Tree balanced
- Removing Items - Demo Easy cases, Hard cases ... We won't do any of them

Last Updated: July 28, 2014 11:41 AM