Trees

Section 1. Skeleton of a binary search tree

If you recall from theory class, a binary search tree is a sorted binary tree (it has two subtrees, left and right). This means that the nodes of the tree follow certain order. If we want to sort the nodes, we will need a key that serves to indicate which node comes first and which one later.

The nodes of a binary search node are sorted in such way that, for each node, the keys of the nodes in its left subtree are lower (or equal), whilst the keys of the nodes in the right subtree are greater (or equal).

Bearing these concepts in mind, and using the concepts you learnt in the previous session with binary trees, we will implement a binary search tree.

More precisely, we will write an implementation of the BSTree<E> (Binary Search Node) interface shown below. For this implementation we will use linked nodes, as in the previous session. Therefore, our binary search tree will be represented by the LBSTree<E> class.

public interface BSTree<E> {

    boolean isEmpty();

    E getInfo();
    Comparable getKey();
    BSTree<E> getLeft();
    BSTree<E> getRight();
    
    String toStringPreOrder();
    String toStringInOrder();
    String toStringPostOrder();
    String toString(); // pre-order

    void insert(Comparable key, E info);

    BSTree<E> search(Comparable key);
}

Before to start implementing the LBSTree<E> class, we need to define the class representing the nodes the tree is made of. Complete the following skeleton for the LBSNode<E> class, which will be in charge of representing the tree nodes.

public class LBSNode<E> {

    private E info;
	private Comparable key;
	private BSTree<E> right;
	private BSTree<E> left;

    public LBSNode(Comparable key, E info, BSTree<E> left, BSTree<E> right;) {
        /* your code here */
    }

    /** Get and set methods */
	
    public String toString() {
        if(info != null) {
            return info.toString();
        } else {
            return "";
        }
    }
}

Pay special attention to the key attribute. Notice that its type is Comparable. Take a look at this interface API. Which method does any key need to implement in order to correctly implement the interface? Take a look at String and Integer APIs. Do they implement the Comparable interface? Could they be used as key?

Next, we are going to actually implement the binary search tree. Observer carefully the BSTree<E> interface, and answer the following questions:

Which methods are new or need to have a different implementation with respect to the binary tree case? Why?
Notice that, in this case, we will not use exception (in order to simplify the implementation). What will the methods do when the tree does not have the requested information? Think about the answer for each of the related methods: getInfo(), getKey(), getRight(), getLeft() y search(Comparable key).

Start implementing the LBSTree<E> class:

Define its attribute(s).
Define two constructors. The first one will create a tree of size 1 (with a node inside), which content (information and key) will be passed as arguments of the constructor. The second constructor will create an empty tree, and therefore will not receive any argument.
Implement the methods defined by the interface, except insert and search methods, that will be the target of the next section.

Solution

public class LBSNode<E> {

    private E info;
    private Comparable key;
    private BSTree<E> right;
    private BSTree<E> left;
	
    public LBSNode(Comparable key, E info, BSTree<E> left, BSTree<E> right) {
        this.info = info;
        this.key = key;
        this.right = right;
        this.left = left;
    }
	
    public E getInfo() {
        return this.info;
    }
	
    public void setInfo(E info) {
        this.info = info;
    }
	
    public Comparable getKey() {
        return this.key;
    }

    public void setKey(Comparable key) {
        this.key = key;
    }
	
    public BSTree<E> getLeft() {
        return this.left;
    }
	
    public void setLeft(BSTree<E> left) {
        this.left = left;
    }
	
    public BSTree<E> getRight() {
        return this.right;
    }
	
    public void setRight(BSTree<E> right) {
        this.right = right;
    }

    public String toString() {
        if(info != null) {
            return info.toString();
        } else {
            return "";
        }
    } 
}

Section 2. Inserting, extracting and searching in a binary search tree

So far, we have the skeleton of our LBSTree<E> class. In this section we will complete it, writing the two most important methods: insert y search.

Implement the void insert(Comparable key, E info) method. It will insert the new information, stored in info, in the corresponding place of the binary search tree, taking into account the key. Remember that if key is lower than the current node's key, you will insert the node in its left subtree; if key is greater, you will insert the node in its right subtree; and if it is equal, you will overwrite the information in the node with the new info. This process is repeated for each node you traverse along the tree, until you reach a node which subtree where you want to add the new information is empty. Therefore, you will need to implement the method using recursion.
Implement the BSTree<E> search(Comparable key) method. It will return the subtree which key is equal to key. If the key is not found, null must be returned. Take advantage of the binary search tree properties in order to search in the most efficient way.

Finally, check your implementation with the LBSTreeTest class.

Solution


public class LBSTree<E> implements BSTree<E> {
	
    private LBSNode<E> root;
	
    public LBSTree(Comparable key, E info) {
        this.root = new LBSNode<E>(key, info, new LBSTree<E>(), new LBSTree<E>());
    }
	
    public LBSTree() {
        this.root = null;
    }
	
    @Override
    public boolean isEmpty() {
        return (this.root == null);
    }

    @Override
    public E getInfo() {
        if (!this.isEmpty()) {
            return this.root.getInfo();
        }
        return null;
    }
	
    @Override
    public Comparable getKey() {
        if (!this.isEmpty()) {
            return this.root.getKey();
        }			
        return null;
    }

    @Override
    public BSTree<E> getLeft() {
        if (!this.isEmpty()) {
            return this.root.getLeft();
        }
        return null;
    }

    @Override
    public BSTree<E> getRight() {
        if (!this.isEmpty()) {
            return this.root.getRight();
        }
        return null;
    }

    @Override
    public String toStringPreOrder() {
        String treeStr = "";
        if(!this.isEmpty()){
            treeStr = this.getInfo().toString();
            if(this.getLeft() != null) {
                treeStr = treeStr + this.getLeft().toStringPreOrder();
            } 
            if(this.getRight() != null) {
                treeStr = treeStr + this.getRight().toStringPreOrder();
            }
        }
        return treeStr;
    }

    @Override
    public String toStringInOrder() {
        String treeStr = "";
        if(!this.isEmpty()){
            if(!this.getLeft().isEmpty()) {
                treeStr = treeStr + this.getLeft().toStringInOrder();
            }
            treeStr = treeStr + this.getInfo().toString();
            if(!this.getRight().isEmpty()) {
                treeStr = treeStr + this.getRight().toStringInOrder();
            }
        }
        return treeStr;
    }

    @Override
    public String toStringPostOrder() {
	    String treeStr = "";
        if(!this.isEmpty()){
            if(this.getLeft() != null) {
                treeStr = treeStr + this.getLeft().toStringPostOrder();
            }
            if(this.getRight() != null) {
                treeStr = treeStr + this.getRight().toStringPostOrder();
            }
            treeStr = treeStr + this.getInfo().toString();
        }
        return treeStr;
    }
	
    public String toString() {
        return this.toStringPreOrder();
    }

    @Override
    public void insert(Comparable key, E info) {
        if(this.isEmpty()) { 
            this.root = new LBSNode<E>(key,info,new LBSTree<E>(), new LBSTree<E>());
        } else {
            if (this.root.getKey().compareTo(key) > 0) {
                // lower key -> insert in the left subtree
                this.getLeft().insert(key,info);

            } else if (this.root.getKey().compareTo(key) < 0) {
                // greater key -> insert in right subtree
                this.getRight().insert(key,info);
		    	
            } else {
                this.root.setInfo(info);
            }
        }
    }

    @Override
    public BSTree<E> search(Comparable key) {
        BSTree<E> searchedSubtree = null;
        if(!this.isEmpty()){
            if(this.root.getKey().compareTo(key) > 0){
                // lower key -> search in the left subtree
                searchedSubtree = this.getLeft().search(key);
            } else if (this.root.getKey().compareTo(key) < 0) {
                // greater key -> insert in the right subtree
                searchedSubtree = this.getRight().search(key);
            } else {
                // equal keys
                searchedSubtree = this;
            }
        } //if reaching an empty subtree -> key not found
        return searchedSubtree;
    }
}

Section 3. Using a binary search tree

Now that we have already implemented our binary search tree, we will see an example of use. In this case, we will create a phone agenda.

The key with which we will sort the agenda will be the name and surnames of each contact. The sorting will work in such a way that first, the first surname will be compared, if they are equal, the second surname will be compared, and if they are also equal, we will consider the name. In order to sort the names, we need a class that will be called Name. This class must implement the Comparable interface. Recall the Comparable interface API. Which method must the Name class implement in order to comply with that interface?

Complete the following skeleton so that the object compared (this) is alphabetically lower than the argument received by the comparison method, you will return -1; if they are the same, 0; and if it is greater, 1. Remember that a name is lower than other one if the first surname is lower (is alphabetically previous) than the first surname of the other name; if both first surnames are the same, we will compare the second surname; and if the second surnames are equal, we will compare the names.

class Name implements Comparable {

    private String name;
    private String firstSurname;
    private String secondSurname;

    public Name(String name, String firstSurname, String secondSurname) {
        this.name = name;
        this.firstSurname = firstSurname;
        this.secondSurname = secondSurname;
    }

    public String getName() {
        return this.name;
    }

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

    public String getFirstSurname() {
        return this.firstSurname;
    }

    public void setFirstsurame(String firstSurname) {
        this.firstSurname = firstSurname;
    }
    
    public String getSecondSurname() {
        return this.secondSurname;
    }

    public void setSecondSurname(String secondSurname) {
        this.secondSurname = secondSurname;
    }
    
    public String toString() {
        return this.firstSurname+" "+this.secondSurname+", "+this.name;
    }
    
    public int compareTo(Object anotherName){
        /** Your code here */
    }
}

We already have the sorting key to be used in our agenda. Now, we need to store all the data of each contact of our agenda, for which we will use the Contact class. Complete the following skeleton with the needed code in the constructor, and adding the get and set methods for every attribute.

class Contact {

    private Name name;
    private int phoneNumber;
    private String postalAddress;

    public Contact(String name, String firstSurname, String secondSurname,
                        int phoneNumber, String postalAdress) {
        /** Your code here */
    }

    /** Get and set methods for every attribute */
    
    public String toString() {
        String contactStr = this.name.toString();
        contactStr = contactStr+"\nPhone: "+this.phoneNumber;
        contactStr = contactStr+"\nAddress: "+this.postalAddress;
        return contactStr;
    }
}

Finally, we will implemente our phone agenda, PhoneAgenda using a binary search tree, so that searching for a contact will be fast and efficient. Implement this class following these guidelines:

Which attributes does PhoneAgenda need?
Define and implement a constructor with no parameters, in which you will initialize the attributes you previously defined.
Create a void insert(String name, String firstSurname, String secondSurname, int phone, String address) method. It will insert a new contact in the agenda. Remember that you have available a Contact class, where the contact's information is sotred, and a Name class, that will be the sorting key of the agenda.
Implement a Contact search(String name, String firstSurname, String secondSurname) method. It will return an object of Contact class containing the data about the contact being searched, or null if that person is not in the agenda.
Implement a void print() method. It will print in the standard output the information of every contact in the agenda, sorted alphabetically. Before writing a single line of code, think which one of the three tree traversal methods (preorder, inorder, postorder) you must use.

Solution

class Name implements Comparable {

    private String name;
    private String firstSurname;
    private String secondSurname;

    public Name(String name, String firstSurname, String secondSurname) {
        this.name = name;
        this.firstSurname = firstSurname;
        this.secondSurname = secondSurname;
    }

    public String getName() {
        return this.name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getFirstSurname() {
        return this.firstSurname;
    }

    public void setFirstSurname(String firstSurname) {
        this.firstSurname = firstSurname;
    }

    public String getSecondSurname() {
        return this.secondSurname;
    }

    public void setSecondSurname(String secondSurname) {
        this.secondSurname = secondSurname;
    }

    public String toString() {
        return this.firstSurname + " " + this.secondSurname + ", " + this.name;
    }

    @Override
    public int compareTo(Object anotherName) {
        if (anotherName != null) {
            if (this.firstSurname.compareTo(((Name) anotherName).getFirstSurname()) < 0) {
                return -1;
            } else if (this.firstSurname.compareTo(((Name) anotherName).getFirstSurname()) > 0) {
                return 1;
            } else {
                if (this.secondSurname.compareTo(((Name) anotherName).getSecondSurname()) < 0) {
                    return -1;
                } else if (this.secondSurname.compareTo(((Name) anotherName).getSecondSurname()) > 0) {
                    return 1;
                } else {
                    if (this.name.compareTo(((Name) anotherName).getName()) < 0) {
                        return -1;
                    } else if (this.name.compareTo(((Name) anotherName).getName()) > 0) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        } 
        return -1;
    }
}

class Contact {

    private Name name;
    private int phoneNumber;
    private String postalAddress;

    public Contact(String name, String firstSurname, String secondSurname,
                        int phoneNumber, String postalAdress) {
        this.name = new Name(name, firstSurname, secondSurname);
        this.phoneNumber = phoneNumber;
        this.postalAddress = postalAdress;
    }

    
    public String getName() {
	    return this.name.getName();
    }

    public void setName(String name) {
	    this.name.setName(name);
    }

    public String getFirstSurname() {
        return this.name.getFirstSurname();
    }

    public void setFirstSurname(String firstSurname) {
        this.name.setFirstSurname(firstSurname);
    }

    public String getSecondSurname() {
        return this.name.getSecondSurname();
    }

    public void setSecondSurname(String secondSurname) {
        this.name.setSecondSurname(secondSurname);
    }
	
    public int getPhoneNumber() {
        return phoneNumber;
    }

    public void setPhoneNumber(int phoneNumber) {
        this.phoneNumber = phoneNumber;
    }

    public String getPostalAddress() {
        return postalAddress;
    }

    public void setPostalAddress(String postalAddress) {
        this.postalAddress = postalAddress;
    }
   
    public String toString() {
        String contactStr = this.name.toString();
        contactStr = contactStr+"\nPhone: "+this.phoneNumber;
        contactStr = contactStr+"\nAddress: "+this.postalAddress+"\n";
        return contactStr;
    }
}


public class PhoneAgenda {

    private BSTree<Contact> agenda;
    
    public PhoneAgenda() {
        agenda = new LBSTree<Contact>();
    }
    
    public void insert(String name, String firstSurname, 
                       String secondSurname, int phone, String address) {
        Contact newContact = new Contact(name, firstSurname, secondSurname, phone, address);
        Name nameKey = new Name(name, firstSurname, secondSurname);
        
        agenda.insert(nameKey, newContact);
    }
    
    public Contact search(String name, String firstSurname, String secondSurname) {
        Name searchedKey = new Name(name, firstSurname, secondSurname);
        BSTree<Contact> searchedContact = agenda.search(searchedKey);
        if(searchedContact != null) {
            return searchedContact.getInfo();
        } else {
            return null;
        }
    }
    
    public void print() {
        System.out.println(agenda.toStringInOrder());
    }
}

Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Trees

1. Session 4 (lab): Trees (II)

1.1. Binary Search Trees

Section 1. Skeleton of a binary search tree

Solution

Section 2. Inserting, extracting and searching in a binary search tree

Solution

Section 3. Using a binary search tree

Solution