1 /*
  2  * Author:    Cameron McKinnon
  3  */
  4 
  5 
  6 
  7 package BinaryTree;
  8 /**
  9  * A node in an AVL Tree. Meant to be used as a private member within the Tree
 10  * class.
 11  * @author Cameron McKinnon
 12  */
 13 public class SubTree<E extends Comparable<E>> implements java.io.Serializable {
 14 
 15     /**
 16      * This node's parent. This pointer is  always maintained automatically by
 17      * functions such as setLeft and setRight, and redirectChildPointer,
 18      * as well as in all rotations.
 19      */
 20     protected SubTree<E> parent;
 21 
 22     /**
 23      * This node's right child.
 24      */
 25     public SubTree<E> right;
 26 
 27     /**
 28      * This node's left child.
 29      */
 30     public SubTree<E> left;
 31 
 32     /**
 33      * The data held by this node - used to compare nodes to one another
 34      */
 35     public E data;
 36 
 37     /**
 38      * The height of this node's two children.
 39      */
 40     private int rightHeight = 0;
 41     private int leftHeight = 0;
 42 
 43     /**
 44      * The balance factor of this tree (used for AVL calculations)
 45      */
 46     private int balanceFactor = 0;
 47 
 48     /**
 49      * The size of this node's two children.
 50      */
 51     private int leftSize = 0;
 52     private int rightSize = 0;
 53 
 54     /**
 55      * Initializes the tree with no parent or children and no data.
 56      */
 57     protected SubTree() {
 58         parent = null;
 59         right = null;
 60         left = null;
 61     }
 62 
 63     /**
 64      * Initializes the tree with no parent or children, and assigns it data.
 65      * @param e The data with which to initialize this node.
 66      */
 67     protected SubTree(E e) {
 68         parent = null;
 69         right = null;
 70         left = null;
 71         data = e;
 72     }
 73 
 74     /**
 75      * Search for and delete a node within this tree whose data is equal to e. Rebalancing
 76      * occurs as appropriate.
 77      * @param e The data to which the to-be-deleted node's data must be equal.
 78      * @return true if a successful deletion occured, or false if no match was found.
 79      */
 80     protected boolean delete(E e) {
 81         SubTree<E> foundNode = findNode(e);
 82         if (foundNode == null) {
 83             return false;
 84         }
 85 
 86         foundNode.deleteMe();
 87         return true;
 88     }
 89 
 90     /**
 91      * Insert a node into this tree (the node will be initialized with data e). If another
 92      * node is found which already contains data equal to e (a collision), no insertion
 93      * will occur.
 94      * @param e The data with which to initialize the node to insert.
 95      * @return true if the node was successfully inserted, or false if there was a
 96      * collision.
 97      */
 98     protected boolean insert(E e) {
 99         if (data == null) {
100             data = e;
101             return true;
102         } else {
103             return (Integer.MAX_VALUE != recursiveInsert(new SubTree<E>(e)));
104         }
105     }
106 
107     /**
108      * Debug this tree recursively using System.out() to display this node's data
109      * and the data of its children.
110      */
111     protected void debug() {
112         System.out.print("\nTREE DEBUG:\nH: ");
113         debug(0);
114     }
115 
116     /**
117      * Compare the data from this node to that of another node.
118      * @param e The node against which this node is being compared.
119      * @return -1 if this node is lesser, 0 if they are equal, or 1 if e is greater.
120      */
121     protected int compareTo(SubTree<E> e) {
122 
123         int r = this.data.compareTo(e.data);
124 
125         if (r > 0) {
126             return 1;
127         }
128         if (r < 0) {
129             return -1;
130         }
131         return 0;
132     }
133 
134     /**
135      * Calculate the size of this tree according to its two childrens' sizes.
136      * @return This SubTree's size.
137      */
138     protected int size() {
139         return leftSize + rightSize + 1;
140     }
141 
142     /**
143      * Return the node at a specific point (ID) in the list generated by an
144      * in-order traversal. NOTE: Although the behaviour of this function is
145      * described that way, this search is actually performed as a binary search,
146      * so it is very fast.
147      * @param i The ID of the node to return (that is, its position in the list
148      *          generated by an in-rder traversal).
149      * @return The found node (or null there is no node with that ID).
150      */
151     protected E getDataAt(int i) {
152         SubTree<E> returnFrom = getNodeByIdRecursive(i, 0);
153         if (returnFrom == null) {
154             return null;
155         }
156         //else
157         return returnFrom.data;
158     }
159 
160     /**
161      * Performs a recursive binary search for an element with i nodes with
162      * values smaller than it. This function is called by getDataAt.
163      * @param i the ID of the node to return
164      * @param add used internally by the function to keep track of how many
165      *        nodes precede the current node - should always be passed a 0
166      *        when called externally!
167      * @return the node at the passed ID, or null if no node was found.
168      */
169     private SubTree<E> getNodeByIdRecursive(int i, int add) {
170         //base case:
171         if (leftSize + add == i) {
172             return this;
173         }
174 
175         //recursive cases:
176         if (leftSize + add > i && left != null) {
177             return left.getNodeByIdRecursive(i, add);
178         } else if (leftSize + add < i && right != null) {
179             return right.getNodeByIdRecursive(i, leftSize + 1 + add);
180         } else {
181             return null;
182         }
183     }
184 
185 
186 
187     /**
188      * Recursively debug this node by displaying its data and the data of its
189      * children
190      * using System.out().
191      * @param i The distance of this node from the root of the tree. Should be
192      *        passed a 0.
193      */
194     private void debug(int i) {
195         fixCounts();
196         //print this node's data:
197         System.out.println(data.toString());
198         //System.out.print(" S="+this.size()+" BF="+(rightHeight - leftHeight));
199 
200         //base case (this is a leaf node):
201         if (left == null && right == null) {
202             return;
203         }
204 
205         i += data.toString().length() + 3;
206 
207         //recursively debug this tree's left child
208         if (left != null) {
209             for (int c = 0; c < i / 2; c++) {
210                 System.out.print("  ");
211             }
212             System.out.print("--L: ");
213             left.debug(i);
214         }
215 
216 
217         //recursively debug this tree's right child
218         if (right != null) {
219             for (int c = 0; c < i / 2; c++) {
220                 System.out.print("  ");
221             }
222             System.out.print("--R: ");
223             right.debug(i);
224         }
225 
226 
227 
228     }
229 
230     /**
231      * Get  the height of this tree by considering its left and right children's
232      * heights.
233      * @return the height of this tree.
234      */
235     private int height() {
236         if (leftHeight > rightHeight) {
237             return leftHeight;
238         } else {
239             return rightHeight;
240         }
241     }
242 
243     /**
244      * Set the right child.
245      * @param newChild The node which will become this node's right child.
246      */
247     private void setRight(SubTree<E> newChild) {
248         right = newChild;
249         if (newChild != null) {
250             rightHeight = newChild.height() + 1;
251             rightSize = newChild.size();
252             newChild.parent = this;
253         } else {
254             rightHeight = 0;
255             rightSize = 0;
256         }
257     }
258 
259     /**
260      * Set the left child.
261      * @param newChild The node which will become this node's left child.
262      */
263     private void setLeft(SubTree<E> newChild) {
264         left = newChild;
265         if (newChild != null) {
266             leftHeight = newChild.height() + 1;
267             leftSize = newChild.size();
268             newChild.parent = this;
269         } else {
270             leftHeight = 0;
271             leftSize = 0;
272         }
273 
274     }
275 
276     /**
277      * Replaces the child oldChild with newChild. That is, whichever of this tree's
278      * children was oldChild will now be newChild.
279      * @param oldChild The current child (to replace).
280      * @param newChild The child with which oldChild is to be replaced.
281      */
282     private void redirectChildPointer(SubTree<E> oldChild, SubTree<E> newChild) {
283         if (right == oldChild) {
284             right = newChild;
285             if (newChild != null) {
286                 rightHeight = newChild.height();
287                 rightSize = newChild.size();
288             }
289         } else if (left == oldChild) {
290             left = newChild;
291             if (newChild != null) {
292                 leftHeight = newChild.height();
293                 leftSize = newChild.size();
294             }
295         } else {
296             right = newChild;
297         }
298 
299         if (newChild != null) {
300             newChild.parent = this;
301         }
302         oldChild.parent=null;
303     }
304 
305     /**
306      * Perform the same actions as setRight, but without maintaining rightHeight.
307      * @param newChild The new right child.
308      */
309     protected void redirectChildPointer(SubTree<E> newChild) {
310         right = newChild;
311         newChild.parent = this;
312     }
313 
314     /**
315      * Perform an AVL right rotation (with root as the root, and pivot as the pivot).
316      * @param root The current root of the tree to be rotated.
317      * @param pivot The node which will become the root after the rotation is done.
318      */
319     private void rightRotate(SubTree<E> root, SubTree<E> pivot) {
320         //redirect the root.parent->root reference to point at pivot instead
321         root.parent.redirectChildPointer(root, pivot);
322         root.setLeft(pivot.right);
323         pivot.setRight(root);
324     }
325 
326     /**
327      * Perform an AVL left rotation (with root as the root, and pivot as the pivot).
328      * @param root The current root of the tree to be rotated.
329      * @param pivot The node which will become the root after the rotation is done.
330      */
331     private void leftRotate(SubTree<E> root, SubTree<E> pivot) {
332         //redirect the root.parent->root reference to point at pivot instead
333         root.parent.redirectChildPointer(root, pivot);
334         root.setRight(pivot.left);
335         pivot.setLeft(root);
336     }
337 
338     /**
339      * Balance _this tree only_ as necessary to make sure its balance factor has a
340      * magnitude of at most 1. Does not go on to balance this tree's children or
341      * ancestors.
342      */
343     private void balance() {
344         balanceFactor = rightHeight - leftHeight;
345         if (balanceFactor == 2) {
346             right.balanceFactor = right.rightHeight - right.leftHeight;
347             if (right.balanceFactor == -1) {
348                 rightRotate(right, right.left);
349             }
350 
351             leftRotate(this, right);
352         } else if (balanceFactor == -2) {
353             left.balanceFactor = left.rightHeight - left.leftHeight;
354             if (left.balanceFactor == 1) {
355                 leftRotate(left, left.right);
356             }
357             rightRotate(this, left);
358         }
359     }
360 
361     /**
362      * Starting with this tree, recursively travel up the tree, balancing it as
363      * we go.
364      */
365     private void balanceUp() {        
366         balance();
367 
368         fixCounts();
369         if (parent != null && parent.parent != null) {
370             parent.balanceUp();
371         }
372     }
373 
374     /**
375      * Recursively find the place for the new node, and insert it there. Then
376      * recursively travel up the tree rebalancing it.
377      * @param e The node to insert.
378      * @return Integer.MAX_VALUE if a collision has occured. Otherwise returns
379      *         the height of this tree.
380      */
381     private int recursiveInsert(SubTree<E> e) {
382         int check = 0;
383 
384         if (e.compareTo(this) == 0) {
385             return Integer.MAX_VALUE;
386         }
387         //if e is greater than this
388         if (e.compareTo(this) > 0) {
389             if (right == null) {
390                 //base case (attach the data as a child of this)
391                 setRight(e);
392                 rightHeight = 1;
393                 rightSize = 1;
394             } else {
395                 //recursive case
396                 check = right.recursiveInsert(e);
397             }
398 
399             //a collision has occured, return the flag
400             if (check == Integer.MAX_VALUE) {
401                 return Integer.MAX_VALUE;
402             }
403             
404             rightHeight = right.height() + 1;
405             rightSize = right.size();
406         }
407         //if e is lesser than this
408         else {
409             if (left == null) {
410                 //base case (attach the data as a child of this)
411                 setLeft(e);
412                 leftHeight = 1;
413                 leftSize = 1;
414             } else {
415                 //recursive case
416                 check = left.recursiveInsert(e);
417             }
418 
419             //a collision has occured, return the flag
420             if (check == Integer.MAX_VALUE) {
421                 return Integer.MAX_VALUE;
422             }
423             leftHeight = left.height() + 1;
424             leftSize = left.size();
425         }
426 
427         //balance the tree if necessary after the insertion
428         balance();
429 
430         //return the new height of this tree (after the balance).
431         return height();
432     }
433 
434     /**
435      * Perform a binary search for a node with data e.
436      * @param e The data to search for.
437      * @return The found node if a match was found, or null if no match was found.
438      */
439     private SubTree<E> findNode(E e) {
440         //normal base case (node found, return this)
441         if (e.compareTo(this.data) == 0) {
442             return this;
443         }
444         //data will be in left subtree
445         else if (e.compareTo(this.data) < 0) {
446             if (left == null) {
447                 //there is no left tree - return null (a base case)
448                 return null;
449             } else {
450                 //recursive case - continue recursing
451                 return left.findNode(e);
452             }
453         }
454         //data will be in right subtree
455         else {
456             if (right == null) {
457                 //there is no right tree - return null (a base case)
458                 return null;
459             } else {
460                 //recursive case - continue recursing
461                 return right.findNode(e);
462             }
463         }
464     }
465 
466     /**
467      * Find the node with the lowest value in this tree.
468      * @return The node with the lowest value in this tree.
469      */
470     private SubTree<E> findLowestNode() {
471         //travel down the left-most branch of this tree until a leaf node is
472         //found
473         if (left == null) {
474             return this;
475         } else {
476             return left.findLowestNode();
477         }
478     }
479 
480     /**
481      * Find the node with the highest value in this tree.
482      * @return The node with the highest value in this tree.
483      */
484     private SubTree<E> findHighestNode() {
485         //travel down the right-most branch of this tree until a leaf node is
486         //found
487         if (right == null) {
488             return this;
489         } else {
490             return right.findHighestNode();
491         }
492     }
493 
494     /**
495      * Find the node whose data is equal to e, and then return its data. Like 
496      * findNode, but returns the found node's data instead of the node itself.
497      * @param e The data to search for.
498      * @return The found data if a match was found, or null if no match was found.
499      */
500     protected E find(E e) {
501         SubTree<E> holder = findNode(e);
502         if (holder == null) {
503             return null;
504         }
505         return holder.data;
506     }
507 
508     /**
509      * Remove this node from its parent tree, and rebalance appropriately. This
510      * function removes the parent's reference to this tree so this tree can be
511      * garbage collected.
512      */
513     private void deleteMe() {
514         if (right == null && left == null) {
515             SubTree<E> oldParent=parent;
516             parent.redirectChildPointer(this, null);
517             oldParent.balanceUp();
518             return;
519         }
520         SubTree<E> replacement;
521         SubTree<E> replacementOldParent;
522 
523         if (right==null){//replace with highest in left subtree
524             //find replacement
525             replacement=left.findHighestNode();
526 
527             //set its old parent
528             replacementOldParent=replacement.parent;
529 
530             //if necessary give replacement's left child to its parent
531             if (this.left!=replacement)
532                 replacement.parent.setRight(replacement.left);
533 
534             //replace this with replacement
535             replacement.setRight(this.right);
536             if (this.left!=replacement)
537                 replacement.setLeft(this.left);
538             //else let replacement keep any children it may have
539             
540             parent.redirectChildPointer(this,replacement);
541 
542         }
543         else{//replace with lowest in right subtree
544             //find replacement
545             replacement=right.findLowestNode();
546 
547             //set its old parent
548             replacementOldParent=replacement.parent;
549             
550             //if necessary give replacement's right child to its parent
551             if (this.right!=replacement)
552                 replacement.parent.setLeft(replacement.right);
553 
554             //replace this with replacement
555             replacement.setLeft(this.left);
556             if (this.right!=replacement)
557                 replacement.setRight(this.right);
558             //else let replacement keep any children it may have
559             parent.redirectChildPointer(this,replacement);
560         }
561 
562         //if this is the replacement's old parent, balance up from replacement
563         if (this==replacementOldParent)
564             replacement.balanceUp();
565         //otherwise balance up from the replacement's old parent
566         else
567             replacementOldParent.balanceUp();
568     }
569 
570     /**
571      * Set leftHeight and rightHeight based on the height of this node's children,
572      * and Set leftSize and rightSize based on the size of this node's children.
573      */
574     private void fixCounts() {
575         if (right == null) {
576             rightHeight = 0;
577             rightSize=0;
578         } else {
579             rightHeight = right.height() + 1;
580             rightSize=right.size();
581         }
582 
583         if (left == null) {
584             leftHeight = 0;
585             leftSize=0;
586         } else {
587             leftHeight = left.height() + 1;
588             leftSize=left.size();
589         }
590     }
591 }
592 
593