|
0
|
1 package datastructures;
|
|
|
2
|
|
|
3 // BinarySearchTree class
|
|
|
4 //
|
|
|
5 // CONSTRUCTION: with no initializer
|
|
|
6 //
|
|
|
7 // ******************PUBLIC OPERATIONS*********************
|
|
|
8 // void insert( x ) --> Insert x
|
|
|
9 // void remove( x ) --> Remove x (unimplemented)
|
|
|
10 // Comparable find( x ) --> Return item that matches x
|
|
|
11 // Comparable findMin( ) --> Return smallest item
|
|
|
12 // Comparable findMax( ) --> Return largest item
|
|
|
13 // boolean isEmpty( ) --> Return true if empty; else false
|
|
|
14 // void makeEmpty( ) --> Remove all items
|
|
|
15 // void printTree( ) --> Print tree in sorted order
|
|
|
16
|
|
|
17 /**
|
|
|
18 * Implements an AVL tree.
|
|
|
19 * Note that all "matching" is based on the compareTo method.
|
|
|
20 * @author Mark Allen Weiss
|
|
|
21 */
|
|
|
22 public class AVLTree
|
|
|
23 {
|
|
|
24 /**
|
|
|
25 * Construct the tree.
|
|
|
26 */
|
|
|
27 public AVLTree( )
|
|
|
28 {
|
|
|
29 root = null;
|
|
|
30 }
|
|
|
31
|
|
|
32 /**
|
|
|
33 * Insert into the tree; duplicates are ignored.
|
|
|
34 * @param x the item to insert.
|
|
|
35 */
|
|
|
36 @SuppressWarnings("unchecked")
|
|
|
37 public void insert(Comparable x )
|
|
|
38 {
|
|
|
39 root = insert( x, root );
|
|
|
40 }
|
|
|
41
|
|
|
42 /**
|
|
|
43 * Remove from the tree. Nothing is done if x is not found.
|
|
|
44 * @param x the item to remove.
|
|
|
45 */
|
|
|
46 @SuppressWarnings("unchecked")
|
|
|
47 public void remove( Comparable x )
|
|
|
48 {
|
|
|
49 System.out.println( "Sorry, remove unimplemented" );
|
|
|
50 }
|
|
|
51
|
|
|
52 /**
|
|
|
53 * Find the smallest item in the tree.
|
|
|
54 * @return smallest item or null if empty.
|
|
|
55 */
|
|
|
56 @SuppressWarnings("unchecked")
|
|
|
57 public Comparable findMin( )
|
|
|
58 {
|
|
|
59 return elementAt( findMin( root ) );
|
|
|
60 }
|
|
|
61
|
|
|
62 /**
|
|
|
63 * Find the largest item in the tree.
|
|
|
64 * @return the largest item of null if empty.
|
|
|
65 */
|
|
|
66 @SuppressWarnings("unchecked")
|
|
|
67 public Comparable findMax( )
|
|
|
68 {
|
|
|
69 return elementAt( findMax( root ) );
|
|
|
70 }
|
|
|
71
|
|
|
72 /**
|
|
|
73 * Find an item in the tree.
|
|
|
74 * @param x the item to search for.
|
|
|
75 * @return the matching item or null if not found.
|
|
|
76 */
|
|
|
77 @SuppressWarnings("unchecked")
|
|
|
78 public Comparable find( Comparable x )
|
|
|
79 {
|
|
|
80 return elementAt( find( x, root ) );
|
|
|
81 }
|
|
|
82
|
|
|
83 /**
|
|
|
84 * Make the tree logically empty.
|
|
|
85 */
|
|
|
86 public void makeEmpty( )
|
|
|
87 {
|
|
|
88 root = null;
|
|
|
89 }
|
|
|
90
|
|
|
91 /**
|
|
|
92 * Test if the tree is logically empty.
|
|
|
93 * @return true if empty, false otherwise.
|
|
|
94 */
|
|
|
95 public boolean isEmpty( )
|
|
|
96 {
|
|
|
97 return root == null;
|
|
|
98 }
|
|
|
99
|
|
|
100 /**
|
|
|
101 * Print the tree contents in sorted order.
|
|
|
102 */
|
|
|
103 public void printTree( )
|
|
|
104 {
|
|
|
105 if( isEmpty( ) )
|
|
|
106 System.out.println( "Empty tree" );
|
|
|
107 else
|
|
|
108 printTree( root );
|
|
|
109 }
|
|
|
110
|
|
|
111 /**
|
|
|
112 * Internal method to get element field.
|
|
|
113 * @param t the node.
|
|
|
114 * @return the element field or null if t is null.
|
|
|
115 */
|
|
|
116 @SuppressWarnings("unchecked")
|
|
|
117 private Comparable elementAt( AVLNode t )
|
|
|
118 {
|
|
|
119 return t == null ? null : t.element;
|
|
|
120 }
|
|
|
121
|
|
|
122 /**
|
|
|
123 * Internal method to insert into a subtree.
|
|
|
124 * @param x the item to insert.
|
|
|
125 * @param t the node that roots the tree.
|
|
|
126 * @return the new root.
|
|
|
127 */
|
|
|
128 @SuppressWarnings("unchecked")
|
|
|
129 private AVLNode insert( Comparable x, AVLNode t )
|
|
|
130 {
|
|
|
131 if( t == null )
|
|
|
132 t = new AVLNode( x, null, null );
|
|
|
133 else if( x.compareTo( t.element ) < 0 )
|
|
|
134 {
|
|
|
135 t.left = insert( x, t.left );
|
|
|
136 if( height( t.left ) - height( t.right ) == 2 )
|
|
|
137 if( x.compareTo( t.left.element ) < 0 )
|
|
|
138 t = rotateWithLeftChild( t );
|
|
|
139 else
|
|
|
140 t = doubleWithLeftChild( t );
|
|
|
141 }
|
|
|
142 else if( x.compareTo( t.element ) > 0 )
|
|
|
143 {
|
|
|
144 t.right = insert( x, t.right );
|
|
|
145 if( height( t.right ) - height( t.left ) == 2 )
|
|
|
146 if( x.compareTo( t.right.element ) > 0 )
|
|
|
147 t = rotateWithRightChild( t );
|
|
|
148 else
|
|
|
149 t = doubleWithRightChild( t );
|
|
|
150 }
|
|
|
151 else
|
|
|
152 ; // Duplicate; do nothing
|
|
|
153 t.height = max( height( t.left ), height( t.right ) ) + 1;
|
|
|
154 return t;
|
|
|
155 }
|
|
|
156
|
|
|
157 /**
|
|
|
158 * Internal method to find the smallest item in a subtree.
|
|
|
159 * @param t the node that roots the tree.
|
|
|
160 * @return node containing the smallest item.
|
|
|
161 */
|
|
|
162 private AVLNode findMin( AVLNode t )
|
|
|
163 {
|
|
|
164 if( t == null )
|
|
|
165 return t;
|
|
|
166
|
|
|
167 while( t.left != null )
|
|
|
168 t = t.left;
|
|
|
169 return t;
|
|
|
170 }
|
|
|
171
|
|
|
172 /**
|
|
|
173 * Internal method to find the largest item in a subtree.
|
|
|
174 * @param t the node that roots the tree.
|
|
|
175 * @return node containing the largest item.
|
|
|
176 */
|
|
|
177 private AVLNode findMax( AVLNode t )
|
|
|
178 {
|
|
|
179 if( t == null )
|
|
|
180 return t;
|
|
|
181
|
|
|
182 while( t.right != null )
|
|
|
183 t = t.right;
|
|
|
184 return t;
|
|
|
185 }
|
|
|
186
|
|
|
187 /**
|
|
|
188 * Internal method to find an item in a subtree.
|
|
|
189 * @param x is item to search for.
|
|
|
190 * @param t the node that roots the tree.
|
|
|
191 * @return node containing the matched item.
|
|
|
192 */
|
|
|
193 @SuppressWarnings("unchecked")
|
|
|
194 private AVLNode find( Comparable x, AVLNode t )
|
|
|
195 {
|
|
|
196 while( t != null )
|
|
|
197 if( x.compareTo( t.element ) < 0 )
|
|
|
198 t = t.left;
|
|
|
199 else if( x.compareTo( t.element ) > 0 )
|
|
|
200 t = t.right;
|
|
|
201 else
|
|
|
202 return t; // Match
|
|
|
203
|
|
|
204 return null; // No match
|
|
|
205 }
|
|
|
206
|
|
|
207 /**
|
|
|
208 * Internal method to print a subtree in sorted order.
|
|
|
209 * @param t the node that roots the tree.
|
|
|
210 */
|
|
|
211 private void printTree( AVLNode t )
|
|
|
212 {
|
|
|
213 if( t != null )
|
|
|
214 {
|
|
|
215 printTree( t.left );
|
|
|
216 System.out.println( t.element );
|
|
|
217 printTree( t.right );
|
|
|
218 }
|
|
|
219 }
|
|
|
220
|
|
|
221 /**
|
|
|
222 * Return the height of node t, or -1, if null.
|
|
|
223 */
|
|
|
224 private static int height( AVLNode t )
|
|
|
225 {
|
|
|
226 return t == null ? -1 : t.height;
|
|
|
227 }
|
|
|
228
|
|
|
229 /**
|
|
|
230 * Return maximum of lhs and rhs.
|
|
|
231 */
|
|
|
232 private static int max( int lhs, int rhs )
|
|
|
233 {
|
|
|
234 return lhs > rhs ? lhs : rhs;
|
|
|
235 }
|
|
|
236
|
|
|
237 /**
|
|
|
238 * Rotate binary tree node with left child.
|
|
|
239 * For AVL trees, this is a single rotation for case 1.
|
|
|
240 * Update heights, then return new root.
|
|
|
241 */
|
|
|
242 private static AVLNode rotateWithLeftChild( AVLNode k2 )
|
|
|
243 {
|
|
|
244 AVLNode k1 = k2.left;
|
|
|
245 k2.left = k1.right;
|
|
|
246 k1.right = k2;
|
|
|
247 k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
|
|
|
248 k1.height = max( height( k1.left ), k2.height ) + 1;
|
|
|
249 return k1;
|
|
|
250 }
|
|
|
251
|
|
|
252 /**
|
|
|
253 * Rotate binary tree node with right child.
|
|
|
254 * For AVL trees, this is a single rotation for case 4.
|
|
|
255 * Update heights, then return new root.
|
|
|
256 */
|
|
|
257 private static AVLNode rotateWithRightChild( AVLNode k1 )
|
|
|
258 {
|
|
|
259 AVLNode k2 = k1.right;
|
|
|
260 k1.right = k2.left;
|
|
|
261 k2.left = k1;
|
|
|
262 k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
|
|
|
263 k2.height = max( height( k2.right ), k1.height ) + 1;
|
|
|
264 return k2;
|
|
|
265 }
|
|
|
266
|
|
|
267 /**
|
|
|
268 * Double rotate binary tree node: first left child
|
|
|
269 * with its right child; then node k3 with new left child.
|
|
|
270 * For AVL trees, this is a double rotation for case 2.
|
|
|
271 * Update heights, then return new root.
|
|
|
272 */
|
|
|
273 private static AVLNode doubleWithLeftChild( AVLNode k3 )
|
|
|
274 {
|
|
|
275 k3.left = rotateWithRightChild( k3.left );
|
|
|
276 return rotateWithLeftChild( k3 );
|
|
|
277 }
|
|
|
278
|
|
|
279 /**
|
|
|
280 * Double rotate binary tree node: first right child
|
|
|
281 * with its left child; then node k1 with new right child.
|
|
|
282 * For AVL trees, this is a double rotation for case 3.
|
|
|
283 * Update heights, then return new root.
|
|
|
284 */
|
|
|
285 private static AVLNode doubleWithRightChild( AVLNode k1 )
|
|
|
286 {
|
|
|
287 k1.right = rotateWithLeftChild( k1.right );
|
|
|
288 return rotateWithRightChild( k1 );
|
|
|
289 }
|
|
|
290
|
|
|
291 /** The tree root. */
|
|
|
292 private AVLNode root;
|
|
|
293
|
|
|
294 }
|
