1   package kiasan.examples.binsearchtree;
2   
3   import kiasan.examples.common.Range;
4   
5   // BinarySearchTree class
6   //
7   // CONSTRUCTION: with no initializer
8   //
9   // ******************PUBLIC OPERATIONS*********************
10  // void insert( x )       --> Insert x
11  // void remove( x )       --> Remove x
12  // Comparable find( x )   --> Return item that matches x
13  // Comparable findMin( )  --> Return smallest item
14  // Comparable findMax( )  --> Return largest item
15  // boolean isEmpty( )     --> Return true if empty; else false
16  // void makeEmpty( )      --> Remove all items
17  // void printTree( )      --> Print tree in sorted order
18  
19  /**
20   * Implements an unbalanced binary search tree. Note that all "matching" is
21   * based on the compareTo method.
22   * 
23   * @author Mark Allen Weiss
24   */
25  public class BinarySearchTree {
26  
27    // Test program
28    public static void main(final String[] args) {
29      final BinarySearchTree t = new BinarySearchTree();
30      final int NUMS = 4000;
31      final int GAP = 37;
32  
33      System.out.println("Checking... (no more output means success)");
34  
35      for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
36        t.insert(i);
37      }
38  
39      for (int i = 1; i < NUMS; i += 2) {
40        t.remove(i);
41      }
42  
43      if (NUMS < 40) {
44        t.printTree();
45        // if( t.findMin( ))).intValue( ) != 2 ||
46        // ((MyInteger)(t.findMax( ))).intValue( ) != NUMS - 2 )
47        // System.out.println( "FindMin or FindMax error!" );
48        //
49        // for( int i = 2; i < NUMS; i+=2 )
50        // if( ((MyInteger)(t.find( new MyInteger( i ) ))).intValue( ) != i )
51        // System.out.println( "Find error1!" );
52        //
53        // for( int i = 1; i < NUMS; i+=2 )
54        // {
55        // if( t.find( new MyInteger( i ) ) != null )
56        // System.out.println( "Find error2!" );
57        // }
58      }
59    }
60  
61    /** The tree root. */
62    public BinaryNode root;
63  
64    /**
65     * Construct the tree.
66     */
67    public BinarySearchTree() {
68      this.root = null;
69    }
70  
71    /**
72     * Internal method to get element field.
73     * 
74     * @param t
75     *          the node.
76     * @return the element field or null if t is null.
77     */
78    private int elementAt(final BinaryNode t) {
81      }
83    }
84  
85    /**
86     * Find an item in the tree.
87     * 
88     * @param x
89     *          the item to search for.
90     * @return the matching item or null if not found.
91     */
92    //@ requires this.repOK();
93    //@ ensures this.repOK();
94    public int find(final int x) {
96    }
97  
98    /**
99     * Internal method to find an item in a subtree.
100    * 
101    * @param x
102    *          is item to search for.
103    * @param t
104    *          the node that roots the tree.
105    * @return node containing the matched item.
106    */
107   private BinaryNode find(final int x, final BinaryNode t) {
110     }
115     } else {
117     }
118   }
119 
120   /**
121    * Find the largest item in the tree.
122    * 
123    * @return the largest item of null if empty.
124    */
125   //@ requires this.repOK();
126   //@ ensures this.repOK();
127   public int findMax() {
129   }
130 
131   /**
132    * Internal method to find the largest item in a subtree.
133    * 
134    * @param t
135    *          the node that roots the tree.
136    * @return node containing the largest item.
137    */
138   private BinaryNode findMax(BinaryNode t) {
142       }
143     }
144 
146   }
147 
148   /**
149    * Find the smallest item in the tree.
150    * 
151    * @return smallest item or null if empty.
152    */
153   //@ requires this.repOK();
154   //@ ensures this.repOK();
155   public int findMin() {
157   }
158 
159   /**
160    * Internal method to find the smallest item in a subtree.
161    * 
162    * @param t
163    *          the node that roots the tree.
164    * @return node containing the smallest item.
165    */
166   private BinaryNode findMin(final BinaryNode t) {
171     }
173   }
174 
175   /**
176    * Insert into the tree; duplicates are ignored.
177    * 
178    * @param x
179    *          the item to insert.
180    */
181 
182   //@ requires this.repOK();
183   //@ ensures this.repOK();
184   public void insert(final int x) {
187 
188   /**
189    * Internal method to insert into a subtree.
190    * 
191    * @param x
192    *          the item to insert.
193    * @param t
194    *          the node that roots the tree.
195    * @return the new root.
196    */
197   private BinaryNode insert(final int x, BinaryNode t) {
204     } else {
205       /* 8 */; // Duplicate; do nothing
206     }
207     /* 9 */
209   }
210 
211   /**
212    * Test if the tree is logically empty.
213    * 
214    * @return true if empty, false otherwise.
215    */
216   public boolean isEmpty() {
217     return this.root == null;
218   }
219 
220   /**
221    * Make the tree logically empty.
222    */
223   public void makeEmpty() {
224     this.root = null;
225   }
226 
227   /**
228    * Print the tree contents in sorted order.
229    */
230   public void printTree() {
231     if (isEmpty()) {
232       System.out.println("Empty tree");
233     } else {
234       printTree(this.root);
235     }
236   }
237 
238   /**
239    * Internal method to print a subtree in sorted order.
240    * 
241    * @param t
242    *          the node that roots the tree.
243    */
244   private void printTree(final BinaryNode t) {
245     if (t != null) {
246       printTree(t.left);
247       System.out.println(t.element);
248       printTree(t.right);
249     }
250   }
251 
252   /**
253    * Remove from the tree. Nothing is done if x is not found.
254    * 
255    * @param x
256    *          the item to remove.
257    */
258   //@ requires this.repOK();
259   //@ ensures this.repOK();
260   public void remove(final int x) {
263 
264   /**
265    * Internal method to remove from a subtree.
266    * 
267    * @param x
268    *          the item to remove.
269    * @param t
270    *          the node that roots the tree.
271    * @return the new root.
272    */
273   private BinaryNode remove(final int x, BinaryNode t) {
276     }
282     {
285     } else {
287     }
289   }
290 
291   boolean repOK() {
294     } else {
296     }
297   }
298 
299   private boolean repOK(final BinaryNode t) {
301   }
302 
303   private boolean repOK(final BinaryNode t, final Range range) {
306     }
309     }
314   }
315 }