Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Trees

Table of Contents

1. Session 4 (lab): Trees (II)
1.1. Binary Search Tree
2. Homework
2.1. Generic (N-ary) Tree
2.2. Priority Queue using a Heap

Lab Section1.  Session 4 (lab): Trees (II)

Exercise Section1.1.  Binary Search Tree

Objective

Teaching the student how to use binary search trees.

Exercise

A binary search tree is an ordered binary tree where, for each node n, all keys from left subtree's nodes are lower than the key of n and all keys from right's subtree are higher (we suppose there are no duplicate keys).

In this exercise, we will implement a binary search tree through both BSTree class (that represents the tree) and BSNode auxiliary class, so that:

  • A BSTree tree has a reference to its root node.

  • A BSNode has the key's comparator, the data to be stored and the nodes references representing both left and right subtrees.

As it is shown in the following figure:

Notice that according to this structure, an empty tree has its root node's reference set to null (however, this does not imply that the tree object is null itself). Next, do the following implementations:

  • Define attributes for BSTree and BSNode classes, according to the structure shown at the previous figure.

  • Provide a constructor, with no parameters, for BSTree class that initializes an empty tree (that is, the one with the root's node set to null). Provide also a constructor for BSNode auxiliary class. This constructor should receive both the node's search key and the data to be stored as parameters. Left and right children subtrees will be initialized to null. For each class, provide necessary get and set access methods.

  • Program a boolean isEmpty() method that tests whether the tree is empty or not.

  • Program a public Object search(Comparable key) method that returns the object that is stored at the node which associated key matches with the one passed in the parameter.

  • Program a public void insert(Comparable key, Object info) method that enters a new data in the tree. To do so, it must create a new node at the correct place, which should contain both the key and the object that are passed in as parameters. If the tree already contains a node with that key, it must overwrite the data stored at the object.

  • Program a void printPreOrder() method that prints to console all tree's entries when traversing it in preorder.

Now that you have experience in the use of trees, let's implement an address agenda using a binary search tree to make searches easier.

  • Program a DirectoryEntry class that stores all data associated with an entry: Name, Surname, Address, Phone, Mobile and Email

  • Program a Directory class that uses a binary search tree to store data from an electronic directory. The search key that is used to order the directory's data is the whole name according to the following format: Surname, Name.

  • Add a void insert(DirectoryEntry data) method to Directory class that enters into the directory all data passed in as parameters. Remember that you must concatenate both Surname and Name to generate the associated search key. Add a void insert() method that enters a new entry into the directory with data input by keyboard.

  • Add a DirectoryEntry search(String fullName) method to Directory that permits to obtain data from a certain entry from the full name (Surname and Name).

  • Program a void printInOrder() method that prints the contents of the directory to console, in alphabetical order (inorder traversal).

Solution

This is the solution: 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/**
 * Directory using a Binary Search tree
 * 
 * @author jfgalvan
 * 
 */
public class Directory {

  private BSTree directory;

  public Directory() {
    directory = new BSTree();
  }

  /**
   * Introduce the data passed as a parameter
   * 
   * @param data
   *          of the new entry
   */
  public void insert(DirectoryEntry data) {

    // Search key
    String key = data.getSurname() + ", " + data.getName();
    System.out.println("** Inserting: " + key);
    directory.insert(key, data);

  }

  /**
   * Introduce a new entry with the data passed through the standard input
   * agenda con los datos que se introduzcan por teclado
   */
  public void insert() throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    DirectoryEntry data = new DirectoryEntry(br);
    br.close();

    insert(data);

  }

  /**
   * Gets the data of a certain entry given a full name (surname and name) *
   * 
   * @param fullName
   *          (Surname, Name)
   * @return searched entry
   */
  public DirectoryEntry search(String fullName) {
    return (DirectoryEntry) directory.search(fullName);
  }

  /**
   * Prints the agenda content in alphabetic order to the standard output
   */
  public void printInOrder() {
    directory.printInOrder();
  }

  public static void main(String[] args) {

    Directory dir = new Directory();

    DirectoryEntry dirEntry = new DirectoryEntry("John", "Smith",
        "Sesame Street", "99999999", "9999999999", "john.smith@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Jimmy", "Johnson", "Waterloo Street",
        "435858098", "4999124909", "jimmy.johnson@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Larry", "Paxson", "Bristol Street",
        "7848892823", "995454549", "larry.paxson@test.com");
    dir.insert(dirEntry);

    dirEntry = new DirectoryEntry("Michael", "Brown", "Generic Street",
        "9984309999", "9991343539", "michael.brown@test.com");
    dir.insert(dirEntry);

    System.out.println("===== Sorted query =====");

    dir.printInOrder();

    System.out
        .println("\n\n===== Now we search for an existing member =====\n");
    dirEntry = dir.search("Paxson, Larry");
    if (dirEntry != null)
      System.out.println(dirEntry.toString());
    else
      System.out.println("Not found!");

    System.out
        .println("\n\n===== Now we search for a non-existing member =====\n");
    dirEntry = dir.search("Paxson, Jimmy");
    if (dirEntry != null)
      System.out.println(dirEntry.toString());
    else
      System.out.println("Not found!");

  }

}

	  
/**
 * Binary Search Tree
 * 
 * @author jfgalvan
 */

public class BSTree {

  /* ********************************************** *
   * CLASS BSNode * **********************************************
   */

  static class BSNode {

    private Comparable key;
    private Object info;
    private BSNode left;
    private BSNode right;

    BSNode(Comparable key, Object info) {
      this(key, info, null, null);
    }

    BSNode(Comparable key, Object info, BSNode l, BSNode r) {
      this.key = key;
      this.info = info;
      left = l;
      right = r;

    }

    Comparable getKey() {
      return key;
    }

    Object getInfo() {
      return info;
    }

    BSNode getLeft() {
      return left;
    }

    BSNode getRight() {
      return right;
    }

    void setInfo(Comparable info) {
      this.info = info;
    }

    void setLeft(BSNode left) {
      this.left = left;
    }

    void setRight(BSNode right) {
      this.right = right;
    }

    public void insert(BSNode tree) throws BTreeException {

      if (tree.getKey().compareTo(this.getKey()) < 0) {
        // lower key -> insert in the left subtree
        if (left != null)
          left.insert(tree);
        else
          left = tree;

      } else if (tree.getKey().compareTo(this.getKey()) > 0) {
        // greater key -> right subtree
        if (right != null)
          right.insert(tree);
        else
          right = tree;

      } else
        throw new BTreeException("Elment already in tree");

    }

    /**
     * Returns the object stored in the node whose key is the same as the one of
     * the key param.
     * 
     * @param key
     *          string to search
     * @return object stored in the searched node
     */
    public Object search(BSNode tree) {

      Object result = null;

      if (tree.getKey().compareTo(this.getKey()) == 0)
        result = this.getInfo();

      else if (tree.getKey().compareTo(this.getKey()) < 0) {
        // If the key to search is lower than the one
        // of the root, search down through the left subtree
        if (left != null)
          result = left.search(tree);

      }

      else {
        // greater key -> right subtree
        if (right != null)
          result = right.search(tree);

      }

      return result;
    }

    void preOrder() {
      System.out.println(info);
      if (left != null)
        left.preOrder();
      if (right != null)
        right.preOrder();
    }

    void inOrder() {
      if (left != null)
        left.inOrder();
      System.out.println(info);
      if (right != null)
        right.inOrder();
    }

    void postOrder() {
      if (left != null)
        left.postOrder();
      if (right != null)
        right.postOrder();
      System.out.println(info);
    }
  }

  /* ********************************************** */

  public static final int LEFT_SIDE = 0;
  public static final int RIGHT_SIDE = 1;

  protected BSNode root;

  BSTree() {
    root = null;
  }

  BSTree(Comparable key, Object info) {
    root = new BSNode(key, info);
  }

  public BSNode getRoot() {
    return root;
  }

  public void setRoot(BSNode root) {
    this.root = root;
  }

  void insert(Comparable key, Object info) {

    BSNode node = new BSNode(key, info);

    if (root == null)
      setRoot(node);
    else {
      try {
        root.insert(node);
      } catch (BTreeException e) {
        System.out.println(e);
      }

    }

  }

  public Object search(String info) {

    BSNode node = new BSNode(info, info);

    return root.search(node);

  }

  /**
   * Check if the tree is empty (no nodes)
   * 
   * @return true if tree is empty; false otherwise
   */
  boolean isEmpty() {
    return (root == null);

  }

  public void printPreOrder() {
    if (root != null)
      root.preOrder();
  }

  public void printInOrder() {
    if (root != null)
      root.inOrder();
  }

  public void printPostOrder() {
    if (root != null)
      root.postOrder();
  }

}
	  
import java.io.BufferedReader;
import java.io.IOException;

/**
 * @author jfgalvan
 * 
 */
public class DirectoryEntry {

  private String name;
  private String surname;
  private String address;
  private String phone;
  private String mobile;
  private String email;

  public DirectoryEntry(String name, String surname, String address,
      String phone, String mobile, String email) {
    this.name = name;
    this.surname = surname;
    this.address = address;
    this.phone = phone;
    this.mobile = mobile;
    this.email = email;
  }

  /**
   * Initialize a new object from the standard input
   */
  public DirectoryEntry(BufferedReader br) throws IOException {

    System.out.print("Introduce the name: ");
    name = br.readLine();

    System.out.print("Introduce the surname: ");
    surname = br.readLine();

    System.out.print("Introduce the address: ");
    address = br.readLine();

    System.out.print("Introduce the phone: ");
    phone = br.readLine();

    System.out.print("Introduce the mobile phone: ");
    mobile = br.readLine();

    System.out.print("Introduce the email address: ");
    email = br.readLine();

  }

  public String getSurname() {
    return surname;
  }

  public String getAddress() {
    return address;
  }

  public String getEmail() {
    return email;
  }

  public String getMobile() {
    return mobile;
  }

  public String getName() {
    return name;
  }

  public String getPhone() {
    return phone;
  }

  public void setSurname(String surname) {
    this.surname = surname;
  }

  public void setAddress(String address) {
    this.address = address;
  }

  public void setEmail(String email) {
    this.email = email;
  }

  public void setMobile(String mobile) {
    this.mobile = mobile;
  }

  public void setName(String name) {
    this.name = name;
  }

  public void setPhone(String phone) {
    this.phone = phone;
  }

  public String toString() {
    return "Data: \n" + surname + ", " + name + "\n" + address + " " + phone
        + " " + mobile + " " + email + "\n" + "--------------";
  }

}

Homework Section2.  Homework

Exercise Section2.1.  Generic (N-ary) Tree

Objective

Teaching the student how to implement and use generic trees, with a variable number of children.

Exercise

This exercise will use the recursive definition of a tree in order to design a Java class that implements an N-ary tree.

Remember that two classes, NTree and NNode, are required in order to represent properly the empty tree.

  • Build a NTree class based on the previous recursive definition. Implement a constructor without parameters that initializes an empty tree. Program an additional constructor that receives just a single parameter, the information (Object class type) to be stored in the root node of the tree.

  • Build a NNode class based on the previous recursive definition, which encapsulates the information to be stored in the node as well as a Vector with the references to the children. Implement a constructor that receives just a single parameter, the information to be stored, (Object class type). Program also the corresponding accessor methods (get and set).

  • Program the size method that returns the number of nodes in the tree.

  • Program the preorder method that prints the elements in the tree applying a preorder traversal.

  • Some auxiliary methods will be also needed for building and traversing the tree, such as int getNumberOfChildren(), void addChild(NNode child), void addChildAt(int index, NNode child), NNode getChildAt(int index), and other.

Solution

This is the solution: 

public class NTree {

  private NNode root;

  public NTree() {
    root = null;
  }

  public NTree(Object info) {
    root = new NNode(info);
  }

  public int size() {
    return root.size();
  }

  public void preorder() {
    root.preorder();
  }

  public NNode getRoot() {
    return root;
  }

  public void setRoot(NNode root) {
    this.root = root;
  }

}
    

import java.util.*;

public class NNode {

  public Object info;
  public Vector<NNode> children;

  /* ************************************************* *
   * Constructor * *************************************************
   */

  public NNode(Object info) {
    this.info = info;
    children = new Vector<NNode>();
  }

  /* ************************************************* *
   * Getters and Setters * *************************************************
   */

  public Object getInfo() {
    return this.info;
  }

  public void setInfo(Object info) {
    this.info = info;
  }

  public Vector<NNode> getChildren() {
    return this.children;
  }

  public void setChildren(Vector<NNode> children) {
    this.children = children;
  }

  /* ************************************************* */

  /**
   * Returns the number of elements in the tree formed by this node and its
   * descendants
   */
  public int size() {
    int size = 1;
    if (children != null)
      for (int i = 0; i < children.size(); i++)
        size += getChildAt(i).size();

    return size;
  }

  /**
   * Prints the tree formed by this node and its descendants following a
   * preorder traversal
   */
  public void preorder() {

    System.out.println("[" + info + "]");

    if (children != null)
      for (int i = 0; i < children.size(); i++)
        getChildAt(i).preorder();

  }

  /* ************************************************* *
   * Other auxiliary methods * *************************************************
   */

  public int getNumberOfChildren() {
    return children.size();
  }

  public boolean hasChildren() {
    return (getNumberOfChildren() > 0);
  }

  public void addChild(NNode child) {
    children.add(child);
  }

  public void addChildAt(int index, NNode child)
      throws IndexOutOfBoundsException {
    children.add(index, child);
  }

  public void removeChildren() {
    this.children = new Vector<NNode>();
  }

  public NNode getChildAt(int index) throws IndexOutOfBoundsException {
    return children.get(index);
  }

  public void removeChildAt(int index) throws IndexOutOfBoundsException {
    children.remove(index);
  }

  public String toString() {
    return getInfo().toString();
  }

  public boolean equals(NNode node) {
    return node.getInfo().equals(getInfo());
  }

}

Exercise Section2.2.  Priority Queue using a Heap

Objective

To study in depth the use of trees by means of binary heaps, implementing a priority queue.

Exercise

A binary heap is a complete ordered binary tree in which data stored at a certain node is lower than data stored at its children nodes. This characteristic allows it to be implemented using a vector and guarantees that its depth is logarithmic.

As it is a complete binary tree, it can be easily represented in a linear model, traversing and storing it by levels (for example, in a Vector ). Given an element at position i , its left child node will be located at the position 2i+1 while its right child node will be at position 2i+2 . Symmetrically, its father will be at position (i-1)/2 . Notice that we also need to know the number of elements of the tree, in order to test whether a node exists or not before accessing its position. Observe the following figure:

Having in mind the previous description:

  • Implement a BinaryHeap class that represents a binary heap, as previously defined, using an inner Vector to store the data. Define all attributes of the class and implement a constructor, with no parameters, that initializes an empty heap. Observe that each heap's element stores two pieces of information: the priority and the object. Program a PriorityQueueElement auxiliary class that encapsulates all of this information.

  • Add to BinaryHeap class the following methods: int size(); that returns the number of elements and boolean isEmpty(); that indicates if the tree is empty or not.

  • Add to BinaryHeap class the void insert(int priority, Object info); method that stores a new element at the heap keeping the structural properties and the heap order.

    To insert an element X at the heap, first of all we have to add a new node to the tree. This node must be added at the end of the structure to guarantee that it remains complete. Once the new element has been added at that final position, the property of heap order must be maintained. To do so, we must test whether the data of the new child node is higher than its father. In such case, the heap is still ordered an the process ends. But, on the other hand, if the new data is lower than the data stored at the father's node, we must swap them and repeat the process of comparison until we reach a node that can be both the root or other node that fulfills the heap principle (father lower or equal than child).

  • Add to BinaryHeap class a Object extract(); method that returns the stored object at the root node, that is, the one with the highest priority, and reorganize the heap so that it maintains its structure and order. Remember that higher priorities correspond to lower values, being 1 the highest priority.

    Return the searched object is trivial because heaps's order property guarantee that it is located at the root node.

    The main difficulty of this method consists of the subsequent reorganization of the heap's structure because the root node can have two childs. That's why it is neccesary to make the opposite process of "refloating" when inserting an element to "sink" the generated "hole" until the correct position.

    To occupy the empty position, we must select the least of the two child nodes of the node (if they exist). The child node swaps with the father so that the "hole" goes down one level. The process repeats until we reach a "leaf" node (that without children)

    The tree still must be complete, so the last element passes to the position in which the "hole" has remained.

  • Add to BinaryHeap class the print() method that prints out to console all stored elements with their priority. Elements must be presented in order, according to their position at the heap.

  • A BBNode node contains the comparison's key, the data to be stored an both references to the left and right subtrees.

  • Modify the definition of BinaryHeap class so that it implementS the PriorityQueue interface. 

    interface PriorityQueue {

  static int MAX_PRIORITY = 1;

  /**
   * Insert the indicated object in the correct position in the queue, depending
   * on its priority. Priority is declared with a natural number (> 0). The
   * bigger is this number, the lower is the element priority associated with
   * the number. The value 1 corresponds to elements with maximum priority.
   */
  void insert(int priority, Object info);

  /**
   * Extract the object with highest priority out of the queue (that is, the one
   * with the minimum priority) In case that several elements have the same high
   * priority, the first introduced (FIFO) will be returned. If queue is empty,
   * null is returned.
   */
  Object extract();

  /**
   * Returns the number of elements in the queue.
   */
  int size();

  /**
   * Indicates if the queue is empty.
   */
  boolean isEmpty();

}

  • Using the BinaryHeap class developed at the previous sections, complete the PrintQueueManager class that manage the printing works by the use of a priority queue. 

    public class PrintQueueManager {

  PriorityQueue queue;

  /**
   * Initialize the manager, empty.
   */
  public PrintQueueManager() {
    // to be completed by the student
  }

  /**
   * Adds a new work to print, with the indicated priority. *
   */
  public void print(int priority, String file) {
    // to be completed by the student

  }

  /**
   * Processes (prints out of the printer) the first work of the queue, with the
   * highest priority, reorganizing the data structure.
   */
  public void process() {
    // to be completed by the student
  }
}

    Observe that the type of the attribute that stores the queue is declared as a PriorityQueue interface. The reason is to make the code as generic as possible so that, in the future, we can change the implementation of the queue with a heap with minimal impact. We recommend you this philosophy for code development, trying to use wherever it is possible the type defined by the interface and avoiding (remember, wherever it is possible) to use references to the class that implements it.

Solution

This is the solution:

heaps.zip