1 /*
  2  * Author:    Cameron McKinnon
  3  */
  4 
  5 package BinaryTree;
  6 
  7 /**
  8  * An AVL Tree that holds any number of data Objects of type E.
  9  * 
 10  * Balance (keeping the tree's height minimal) and order (ensuring the tree is
 11  * sorted) are both automatically maintained.
 12  *
 13  * 
 14  * @param <E> The type of data to be sorted by this Tree.
 15  * @author Cameron McKinnon
 16  */
 17 public class Tree<E extends Comparable<E>>
 18         implements java.io.Serializable {
 19 
 20     /**
 21      * overseer is used internally to keep track of the tree's root after
 22      * rotations.
 23      */
 24     protected SubTree<E> overseer;
 25 
 26     /**
 27      * Insert a node into the Tree. This node will contain toInsert. If another
 28      * node is found that contains data which exactly matches toInsert
 29      * (a collision), no insertion will take place and the Tree will not be
 30      * changed.
 31      * @param toInsert The node to insert.
 32      * @return true on a successful insert, or false on a collision.
 33      */
 34     public boolean insert(E toInsert) {
 35         return overseer.right.insert(toInsert);
 36     }
 37 
 38     /**
 39      * Search for a node which holds data equal to toFind.
 40      * @param toFind The data to search for.
 41      * @return the data held by the node if a matching one was found, or
 42      * null if no match was found.
 43      */
 44     public E find(E toFind) {
 45         return overseer.right.find(toFind);
 46     }
 47 
 48     /**
 49      * Delete the node with data toDelete from the tree.
 50      * @param toDelete The node to be deleted will contain this data.
 51      * @return true if a node was found and deleted, or false if no match was found.
 52      */
 53     public boolean delete(E toDelete) {
 54         if (size()==1){
 55             //special case where there's only one node left
 56             //(set to null instead of deleting)
 57             if (overseer.right.data.compareTo(toDelete)==0){
 58                 overseer.right.data=null;
 59                 return true;
 60             }
 61             return false;
 62         }
 63         else
 64             return overseer.right.delete(toDelete);
 65     }
 66 
 67     /**
 68      * For debugging purposes only (not recommended for production use!): Display a
 69      * visual representation of the tree's nodes using System.out(). Each node is
 70      * represented by the data it contains.
 71      */
 72     public void debug() {
 73         overseer.right.debug();
 74     }
 75 
 76 
 77     /**
 78      * In an in-order list of all the nodes in this tree, get the data from the
 79      * child node at a specific position (ID). (Allows array-like data retrieval).
 80      * This function performs a binary search.
 81      * @param i the ID ('position') of the item to return.
 82      * @return the data of the ndoe found, or null if no node was found
 83      */
 84     public E getChildAt(int i) {
 85         return overseer.right.getDataAt(i);
 86     }
 87 
 88     /**
 89      * Get the number of nodes in this tree.
 90      * @return the number of nodes in this tree.
 91      */
 92     public int size() {
 93         if (overseer.right.data == null) {
 94             return 0;
 95         } else {
 96             return overseer.right.size();
 97         }
 98     }
 99 
100     /**
101      * @return true if the tree is empty - false otherwise.
102      */
103     public boolean isEmpty(){
104         return (overseer.right.data == null);
105     }
106 
107     
108 
109     /**
110      * Initialize the tree with no data.
111      */
112     public Tree() {
113         overseer = new SubTree<E>();
114         overseer.redirectChildPointer(new SubTree<E>());
115     }
116 
117     /**
118      * Initialize the tree with one node of data.
119      * @param initData The data with which to initialize the tree. Immediately 
120      * after this constructor is called, the only node in the tree will be initData.
121      */
122     public Tree(E initData) {
123         overseer = new SubTree<E>();
124         overseer.redirectChildPointer(new SubTree<E>());
125         insert(initData);
126     }
127 }
128 
129