1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22 import static junit.framework.Assert.assertEquals;
23 import static org.junit.Assert.assertFalse;
24 import static org.junit.Assert.assertNotNull;
25 import static org.junit.Assert.assertNull;
26 import static org.junit.Assert.assertTrue;
27
28 import java.util.ArrayList;
29 import java.util.Comparator;
30 import java.util.List;
31
32 import org.junit.Before;
33 import org.junit.Test;
34 import org.slf4j.Logger;
35 import org.slf4j.LoggerFactory;
36
37
38
39
40
41
42
43 public class AvlTreeTest
44 {
45
46 AvlTree<Integer> tree;
47
48 private static final Logger LOG = LoggerFactory.getLogger( AvlTreeTest.class );
49
50 @Before
51 public void createTree()
52 {
53 tree = new AvlTree<Integer>( new Comparator<Integer>()
54 {
55
56 public int compare( Integer i1, Integer i2 )
57 {
58 return i1.compareTo( i2 );
59 }
60
61 });
62 }
63
64
65 @Test
66 public void testEmpty()
67 {
68 assertTrue( tree.isEmpty() );
69 assertNull( tree.getFirst() );
70 assertNull( tree.getLast() );
71
72 tree.remove( 97 );
73 assertTrue( tree.isEmpty() );
74
75 if( LOG.isDebugEnabled() )
76 {
77 tree.printTree();
78 }
79 }
80
81
82 @Test
83 public void testFirstAndLast()
84 {
85 tree.insert( 7 );
86 assertFalse( tree.isEmpty() );
87 assertNotNull( tree.getFirst() );
88 assertNotNull( tree.getLast() );
89
90 tree.insert( 10 );
91 assertEquals( 2, tree.getSize() );
92 assertNotNull( tree.getFirst() );
93 assertNotNull( tree.getLast() );
94 assertFalse( tree.getFirst().equals( tree.getLast() ) );
95 assertTrue( tree.getFirst().getKey().equals( 7 ) );
96 assertTrue( tree.getLast().getKey().equals( 10 ) );
97
98 tree.insert( 3 );
99 assertTrue( tree.getFirst().getKey().equals( 3 ) );
100 assertTrue( tree.getLast().getKey().equals( 10 ) );
101
102 tree.insert( 11 );
103 assertTrue( tree.getFirst().getKey().equals( 3 ) );
104 assertTrue( tree.getLast().getKey().equals( 11 ) );
105 }
106
107
108 @Test
109 public void testInsert()
110 {
111 assertNull( tree.insert( 3 ) );
112 assertFalse( tree.isEmpty() );
113
114 assertTrue( 3 == tree.insert( 3 ) );
115 assertTrue( 1 == tree.getSize() );
116
117 assertNotNull( tree.getFirst() );
118 assertNotNull( tree.getLast() );
119 assertTrue( tree.getFirst() == tree.getLast() );
120
121 tree.remove( 3 );
122
123 tree.insert( 37 );
124 tree.insert( 70 );
125 tree.insert( 12 );
126 assertTrue( 3 == tree.getSize() );
127
128 tree.insert( 90 );
129 tree.insert( 25 );
130 tree.insert( 99 );
131 tree.insert( 91 );
132 tree.insert( 24 );
133 tree.insert( 28 );
134 tree.insert( 26 );
135
136 if( LOG.isDebugEnabled() )
137 {
138 tree.printTree();
139 }
140
141 tree.remove( 24 );
142 if( LOG.isDebugEnabled() )
143 {
144 tree.printTree();
145 }
146 assertTrue( tree.getRoot().getLeft().key == 26 );
147 }
148
149
150 @Test
151 public void testSingleRightRotation()
152 {
153
154 tree.insert( 3 );
155 tree.insert( 2 );
156 tree.insert( 1 );
157
158 assertEquals("1,2,3", getInorderForm());
159 }
160
161 @Test
162 public void testSingleLeftRotation()
163 {
164
165 tree.insert( 1 );
166 tree.insert( 2 );
167 tree.insert( 3 );
168
169 assertEquals("1,2,3", getInorderForm());
170 }
171
172
173 @Test
174 public void testDoubleLeftRotation()
175 {
176
177 tree.insert( 1 );
178 tree.insert( 3 );
179 tree.insert( 2 );
180
181 assertEquals("1,2,3", getInorderForm());
182 }
183
184 @Test
185 public void testDoubleRightRotation()
186 {
187
188 tree.insert( 3 );
189 tree.insert( 1 );
190 tree.insert( 2 );
191 assertEquals("1,2,3", getInorderForm());
192 }
193
194 @Test
195 public void testLinks()
196 {
197 tree.insert( 37 );
198 tree.insert( 1 );
199 tree.insert( 2 );
200 tree.insert( 10 );
201 tree.insert( 11 );
202 tree.insert( 25 );
203 tree.insert( 5 );
204
205 assertTrue( 1 == tree.getFirst().key );
206 assertTrue( 37 == tree.getLast().key );
207 }
208
209 @Test
210 public void testRemove()
211 {
212 tree.insert( 3 );
213 tree.insert( 2 );
214 tree.insert( 1 );
215
216 LOG.debug(getLinkedText());
217 tree.remove( 2 );
218 LOG.debug(getLinkedText());
219 assertEquals("1,3", getInorderForm());
220
221 tree.remove( 1 );
222 assertEquals("3", getInorderForm());
223 assertTrue( 3 == tree.getRoot().key );
224
225 assertNull( tree.remove( 777 ) );
226 assertTrue( 3 == tree.remove( 3 ) );
227 assertTrue(tree.isEmpty());
228
229 tree.insert( 37 );
230 tree.insert( 39 );
231 tree.insert( 27 );
232 tree.insert( 38 );
233 tree.insert( 21 );
234 tree.insert( 26 );
235 tree.insert( 43 );
236 assertEquals( "21,26,27,37,38,39,43", getInorderForm() );
237
238 tree.remove( 26 );
239 assertEquals( "21,27,37,38,39,43", getInorderForm() );
240
241 tree.remove( 43 );
242 assertEquals( "21,27,37,38,39", getInorderForm() );
243
244 tree.remove( 39 );
245 assertEquals( "21,27,37,38", getInorderForm() );
246
247 assertTrue( 37 == tree.getRoot().key );
248
249 tree.remove( 38 );
250 assertTrue( 27 == tree.getRoot().key );
251 assertEquals( "21,27,37", getInorderForm() );
252
253 if( LOG.isDebugEnabled() )
254 {
255 tree.printTree();
256 }
257 }
258
259 @Test
260 public void testLinkedNodes()
261 {
262 for( int i=0; i< 3; i++)
263 {
264 tree.insert( i );
265 }
266
267 assertEquals( "[0]-->[1]-->[2]-->NULL", getLinkedText());
268
269 tree.remove( 1 );
270 assertEquals( "[0]-->[2]-->NULL", getLinkedText());
271
272 tree.insert( 4 );
273 tree.insert( 3 );
274
275 assertEquals( "[0]-->[2]-->[3]-->[4]-->NULL", getLinkedText());
276
277 tree.remove( 0 );
278 assertEquals( "[2]-->[3]-->[4]-->NULL", getLinkedText());
279
280 tree.remove( 3 );
281 assertEquals( "[2]-->[4]-->NULL", getLinkedText());
282 }
283
284 @Test
285 public void testFind()
286 {
287 tree.insert( 1 );
288 tree.insert( 70 );
289 tree.insert( 21 );
290 tree.insert( 12 );
291 tree.insert( 27 );
292 tree.insert( 11 );
293
294 assertNotNull( tree.find( 11 ) );
295 assertNull( tree.find( 0 ));
296
297 tree.setRoot( null );
298 assertNull( tree.find( 3 ));
299 }
300
301 @Test
302 public void testFindGreater()
303 {
304 assertNull( tree.findGreater( 1 ) );
305
306 tree.insert( 1 );
307 assertNull( tree.findGreater( 1 ) );
308
309 tree.insert( 0 );
310 tree.insert( 3 );
311 tree.insert( 7 );
312 tree.insert( 6 );
313 tree.insert( 2 );
314 tree.insert( 8 );
315
316 assertFalse( 1 == tree.findGreater( 1 ).key );
317 assertTrue( 2 == tree.findGreater( 1 ).key );
318 assertTrue( 6 == tree.findGreater( 4 ).key );
319 assertNull( tree.findGreater( 8 ) );
320 }
321
322 @Test
323 public void testFindLess()
324 {
325 assertNull( tree.findLess( 1 ) );
326
327 tree.insert( 1 );
328 assertNull( tree.findLess( 1 ) );
329
330 tree.insert( 2 );
331 tree.insert( 7 );
332 tree.insert( 3 );
333 tree.insert( 6 );
334 tree.insert( 0 );
335 tree.insert( 37 );
336
337 assertFalse( 0 == tree.findLess( 5 ).key );
338 assertTrue( 3 == tree.findLess( 5 ).key );
339 assertTrue( 7 == tree.findLess( 8 ).key );
340 assertNull( tree.findLess( 0 ) );
341 }
342
343 @Test
344 public void testFindMaxMin()
345 {
346 tree.insert( 72 );
347 tree.insert( 79 );
348
349 tree.remove( 72 );
350 assertTrue( 79 == tree.getRoot().key );
351
352 tree.insert( 11 );
353 tree.remove( 79 );
354 assertTrue( 11 == tree.getRoot().key );
355 }
356
357 @Test
358 public void testGetKeys()
359 {
360 tree.insert( 72 );
361 tree.insert( 79 );
362 tree.insert( 1 );
363 tree.insert( 2 );
364 tree.insert( 3 );
365 tree.insert( 7 );
366 tree.insert( 34 );
367
368 assertTrue( 7 == tree.getKeys().size() );
369 }
370
371 @Test
372 public void testTreeRoationAtLeftChildAfterDeletingRoot()
373 {
374 int[] keys = { 86, 110, 122, 2, 134, 26, 14, 182 };
375 int[] expectedKeys = { 2, 14, 26, 86, 122, 134, 182 };
376
377 for( int key:keys )
378 {
379 tree.insert( key );
380 }
381
382 tree.remove( 110 );
383
384 for ( int key : expectedKeys )
385 {
386 assertNotNull( "Should find " + key, tree.find( key ) );
387 }
388 }
389
390
391 @Test
392 public void testDetachNodesAtLeftChildAfterDeletingRoot()
393 {
394 int[] keys = { 110, 122, 2, 134, 86, 14, 26, 182 };
395
396 for( int key:keys )
397 {
398 tree.insert( key );
399 }
400
401 tree.remove( 110 );
402
403 assertEquals( 26, ( int ) tree.find( 14 ).right.key );
404 }
405
406
407 @Test
408 public void testRemoveInRightSubtree()
409 {
410 int[] keys = { 8, 4, 13, 6, 15, 7, 10, 5, 14, 2, 11, 3, 9, 1 };
411
412 for( int key:keys )
413 {
414 tree.insert( key );
415 }
416
417 tree.remove( 13 );
418
419 assertEquals( 11, ( int ) tree.find( 8 ).right.key );
420 }
421
422
423 @Test
424 public void testRemoveInLeftSubtree()
425 {
426 int[] keys = { 8, 4, 12, 6, 7, 16, 10, 5, 11, 9, 17, 5, 14, 2, 13, 1, 3 };
427
428 for( int key:keys )
429 {
430 tree.insert( key );
431 }
432
433 tree.remove( 16 );
434
435 assertEquals( 8, ( int ) tree.getRoot().key );
436 assertEquals( 12, ( int ) tree.getRoot().right.key );
437 assertEquals( 14, ( int ) tree.getRoot().right.right.key );
438 assertEquals( 13, ( int ) tree.find( 14 ).left.key );
439 }
440
441
442 private String getLinkedText()
443 {
444 LinkedAvlNode<Integer> first = tree.getFirst();
445 StringBuilder sb = new StringBuilder();
446
447 while( first != null )
448 {
449 sb.append( first )
450 .append( "-->" );
451
452 first = first.next;
453 }
454 sb.append( "NULL" );
455 return sb.toString();
456 }
457
458 private String getInorderForm()
459 {
460 StringBuilder sb = new StringBuilder();
461 List<LinkedAvlNode<Integer>> path = new ArrayList<LinkedAvlNode<Integer>>();
462
463 traverse( tree.getRoot(), path );
464 int i;
465 for( i=0; i < path.size() -1; i++ )
466 {
467 sb.append( path.get( i ).key )
468 .append( ',' );
469 }
470
471 sb.append( path.get( i ).key );
472
473 return sb.toString();
474 }
475
476 private void traverse( LinkedAvlNode<Integer> startNode, List<LinkedAvlNode<Integer>> path )
477 {
478
479
480 if( startNode.left != null )
481 {
482 traverse( startNode.left, path );
483 }
484
485 path.add( startNode );
486
487 if( startNode.right != null )
488 {
489 traverse( startNode.right, path );
490 }
491
492 }
493 }