Mercurial > repos > pfrommolt > ngsrich

comparison NGSrich_0.5.5/src/datastructures/AVLTree.java @ 0:89ad0a9cca52 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author pfrommolt
date Mon, 21 Nov 2011 08:12:19 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:89ad0a9cca52
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 }