1   package kiasan.examples.avltree;
2   
3   import kiasan.examples.common.Range;
4   
5   /**
6    * Implements an AVL tree. Note that all "matching" is based on the compareTo
7    * method.
8    * 
9    * @author Mark Allen Weiss
10   */
11  public class AvlTree {
12    /**
13     * Double rotate binary tree node: first left child with its right child; then
14     * node k3 with new left child. For AVL trees, this is a double rotation for
15     * case 2. Update heights, then return new root.
16     */
17    private static AvlNode doubleWithLeftChild(final AvlNode k3) {
20    }
21  
22    /**
23     * Double rotate binary tree node: first right child with its left child; then
24     * node k1 with new right child. For AVL trees, this is a double rotation for
25     * case 3. Update heights, then return new root.
26     */
27    private static AvlNode doubleWithRightChild(final AvlNode k1) {
30    }
31  
32    /**
33     * Return the height of node t, or -1, if null.
34     */
35    private static int height(final AvlNode t) {
37    }
38  
39    /**
40     * Return maximum of lhs and rhs.
41     */
42    private static int max(final int lhs, final int rhs) {
44    }
45  
46    /**
47     * Rotate binary tree node with left child. For AVL trees, this is a single
48     * rotation for case 1. Update heights, then return new root.
49     */
50    private static AvlNode rotateWithLeftChild(final AvlNode k2) {
57    }
58  
59    /**
60     * Rotate binary tree node with right child. For AVL trees, this is a single
61     * rotation for case 4. Update heights, then return new root.
62     */
63    private static AvlNode rotateWithRightChild(final AvlNode k1) {
70    }
71  
72    /** The tree root. */
73    private AvlNode root;
74  
75    /**
76     * Construct the tree.
77     */
78    public AvlTree() {
79      this.root = null;
80    }
81  
82    boolean balanced() {
84    }
85  
86    private boolean balanced(final AvlNode an) {
89      }
94    }
95  
96    /**
97     * Internal method to get element field.
98     * 
99     * @param t
100    *          the node.
101    * @return the element field or null if t is null.
102    */
103   private int elementAt(final AvlNode t) {
105   }
106 
107   /**
108    * Find an item in the tree.
109    * 
110    * @param x
111    *          the item to search for.
112    * @return the matching item or null if not found.
113    */
114   //@ requires this.ordered() && this.wellFormed() && this.balanced();
115   //@ ensures this.ordered() && this.wellFormed() && this.balanced();
116   public int find(final int x) {
118   }
119 
120   /**
121    * Internal method to find an item in a subtree.
122    * 
123    * @param x
124    *          is item to search for.
125    * @param t
126    *          the node that roots the tree.
127    * @return node containing the matched item.
128    */
129   private AvlNode find(final int x, AvlNode t) {
135       } else {
137       }
138     }
139 
141   }
142 
143   /**
144    * Find the largest item in the tree.
145    * 
146    * @return the largest item of null if empty.
147    */
148   //@requires this.ordered() && this.wellFormed() && this.balanced();
149   //@ensures this.ordered() && this.wellFormed() && this.balanced() && this.maxElement(\result);
150   public int findMax() {
152   }
153 
154   /**
155    * Internal method to find the largest item in a subtree.
156    * 
157    * @param t
158    *          the node that roots the tree.
159    * @return node containing the largest item.
160    */
161   private AvlNode findMax(AvlNode t) {
164     }
165 
168     }
170   }
171 
172   /**
173    * Find the smallest item in the tree.
174    * 
175    * @return smallest item or null if empty.
176    */
177   //@requires this.ordered() && this.wellFormed() && this.balanced();
178   //@ensures this.ordered() && this.wellFormed() && this.balanced() && this.minElement(\result);
179   public int findMin() {
181   }
182 
183   /**
184    * Internal method to find the smallest item in a subtree.
185    * 
186    * @param t
187    *          the node that roots the tree.
188    * @return node containing the smallest item.
189    */
190   private AvlNode findMin(AvlNode t) {
193     }
194 
197     }
199   }
200 
201   /**
202    * Insert into the tree; duplicates are ignored.
203    * 
204    * @param x
205    *          the item to insert.
206    */
207   //@ requires ordered() && wellFormed() && balanced();
208   //@ ensures balanced() && ordered();
209   public void insert(final int x) {
212 
213   /**
214    * Internal method to insert into a subtree.
215    * 
216    * @param x
217    *          the item to insert.
218    * @param t
219    *          the node that roots the tree.
220    * @return the new root.
221    */
222   private AvlNode insert(final int x, AvlNode t) {
230         } else {
232         }
233       }
239         } else {
241         }
242       }
243     } else {
244       ; // Duplicate; do nothing
245     }
248   }
249 
250   /**
251    * Test if the tree is logically empty.
252    * 
253    * @return true if empty, false otherwise.
254    */
255   public boolean isEmpty() {
256     return this.root == null;
257   }
258 
259   /**
260    * Make the tree logically empty.
261    */
262   public void makeEmpty() {
263     this.root = null;
264   }
265 
266   boolean maxElement(final int max) {
268   }
269 
270   private boolean maxElement(final int max, final AvlNode t) {
273     }
275       return false;
276     }
278   }
279 
280   boolean minElement(final int min) {
282   }
283 
284   private boolean minElement(final int min, final AvlNode t) {
287     }
289       return false;
290     }
292   }
293 
294   boolean ordered() {
296   }
297 
298   private boolean ordered(final AvlNode t, final Range range) {
301     }
304     }
309   }
310 
311   /**
312    * Print the tree contents in sorted order.
313    */
314   public void printTree() {
315     if (isEmpty()) {
316       System.out.println("Empty tree");
317     } else {
318       printTree(this.root);
319     }
320   }
321 
322   /**
323    * Internal method to print a subtree in sorted order.
324    * 
325    * @param t
326    *          the node that roots the tree.
327    */
328   private void printTree(final AvlNode t) {
329     if (t != null) {
330       printTree(t.left);
331       System.out.println(t.element);
332       printTree(t.right);
333     }
334   }
335 
336   /**
337    * Remove from the tree. Nothing is done if x is not found.
338    * 
339    * @param x
340    *          the item to remove.
341    */
342   public void remove(final int x) {
343     // System.out.println( "Sorry, remove unimplemented" );
344   }
345 
346   boolean wellFormed() {
348   }
349 
350   private boolean wellFormed(final AvlNode an) {
353     }
357     }
359   }
360 }