Trees

Thus far we have learned about Lists, Sets, Stacks, Queues, and Linked Lists. Each of them holds data in a linear way: Each piece of data is held in a logical way, there is a definite start and end and each element occupies a single spot in the data structure.

This is not the only way to organize data, however. A branching structure where one element can make reference to multiple other elements allows for much quicker searching and sorting of elements.

This branching structure is called a Tree. Tree's are composed of Nodes, similar to the ones used in the Linked List. These Nodes, however will have multiple Nodes as children:

In this example, we have a set of integers, arranged in a tree. The 8 Node is the parent of 2 children: 3 and 10.

We can also identify the 8 Node as the root of the tree. On the other hand, 1, 4, 7 and 13 are called leaf nodes because they have no children.

Some other terminology of note:

  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is a height of the root.

The Node object created for Trees might look something like the Java code provided below:

public class Node<E extends Comparable> {

    private E data;
    private Node<E> leftChild;
    private Node<E> rightChild;

    public Node(E data) {
        this.data = data;
    }

    public Node getLeft() {
        return leftChild;
    }

    public void setLeft(Node<E> leftChild) {
        this.leftChild = leftChild;
    }

    public Node getRight() {
        return leftChild;
    }

    public void setRight(Node<E> rightChild) {
        this.rightChild = rightChild;
    }

    public E getData() {
        return data;
    }
}

Our Node class strictly implements a left and right child. This makes our data structure a Binary Tree. It is possible to have trees that have more than two children, but we will be working strictly with Binary Trees.

By necessity, Binary Trees need to be able to compare elements in order to know where to place them in the tree, and thus Binary Trees are excellent at sorting comparable objects. As a consequence, insertion and searching using a tree is very efficient. We will see this with the implementation of the ISimpleTree<E> interface.

One thing that is a complicated about a tree object is deletion. This is because there are several cases to consider:

  • The data does not exist in the tree
  • The data is in a leaf
  • The data Node has only one child
  • The data Node has two children

We will cover this in more depth when we cover recursion. For now we will only consider insertion of new elements.

Some other, potentially useful things you could do to the Node<E> class to make your tree more useful:

  • Add a setData method to allow for replacement of data. This is a less useful feature in a Tree than in other data structures.
  • Add a instance variable that allows the Node object to know its parent Node.

Insertion

In order to insert an element into the Tree we need something that gives us a little more information than the equals method that exists on objects. For this we will be using the compareTo method. You may have noticed that the Node class and ISimpleTree interface both have "E extends Comparable." This allows us to ensure that the data types we are using all have the compareTo method available.

The compareTo method returns an integer rather than a Boolean. The integer tells us which object should be placed first. Consider the following code comparing two strings:

someString.compareTo(otherString);

We can identify which string (someString or otherString) by looking at the return value from the compareTo method. If the return value is:

  • 0, then someString and otherString are the equivalent.
  • less than 0, then someString comes BEFORE otherString, lexicographically. Usually these values are stored in the leftChild of the Node.
  • greater than 0, then someString comes AFTER otherString, lexicographically. Usually these values are stored in the rightChild of the Node.

Once we understand this, we simply traverse the tree (called walking the tree) using compareTo until we find a null child Node that satisfies our comparison and insert the input value there.

public interface ISimpleTree<E extends Comparable> {
    /**
     * Inserts an element into the tree.
     * @param element - the element to be inserted
     */
    void insert(E element);

    /**
     * Clears all elements from the tree
     */
    void clear();

    /**
     * Deletes an element in the tree, if it exists.
     * NOT CURRENTLY IMPLEMENTED.
     * @param element - the element to be deleted
     * @return boolean true if and only if the elmenent was
     *         removed from the tree.
     */
    boolean delete(E element);

    /**
     * Returns a count of the number of elements in the tree
     * @return int - the number of elements in the tree.
     */
    int size()
}

Files: