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
23 import java.util.ArrayList;
24 import java.util.Comparator;
25 import java.util.List;
26
27
28
29
30
31
32
33
34 public class AvlTree<K>
35 {
36
37 private LinkedAvlNode<K> root;
38
39
40 private Comparator<K> comparator;
41
42
43 private LinkedAvlNode<K> first;
44
45
46 private LinkedAvlNode<K> last;
47
48
49
50
51
52
53
54 public AvlTree( Comparator<K> comparator)
55 {
56 this.comparator = comparator;
57 }
58
59
60
61
62
63 public Comparator<K> getComparator()
64 {
65 return comparator;
66 }
67
68
69
70
71
72
73
74
75
76 public K insert( K key )
77 {
78 LinkedAvlNode<K> node, temp;
79 LinkedAvlNode<K> parent = null;
80 int c;
81
82 if ( root == null )
83 {
84 root = new LinkedAvlNode<K>( key );
85 first = root;
86 last = root;
87 return null;
88 }
89
90 node = new LinkedAvlNode<K>( key );
91
92 temp = root;
93
94 List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
95
96 while( temp != null )
97 {
98 treePath.add(0, temp );
99 parent = temp;
100
101 c = comparator.compare( key, temp.getKey() );
102
103 if( c == 0 )
104 {
105 return key;
106 }
107
108 if( c < 0 )
109 {
110 temp.isLeft = true;
111 temp = temp.getLeft();
112 }
113 else
114 {
115 temp.isLeft = false;
116 temp = temp.getRight();
117 }
118 }
119
120 if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 )
121 {
122 parent.setLeft( node );
123 }
124 else
125 {
126 parent.setRight( node );
127 }
128
129 insertInList( node, parent, c );
130
131 treePath.add( 0, node );
132 balance(treePath);
133
134 return null;
135 }
136
137
138 private void removeFromList(LinkedAvlNode<K> node)
139 {
140 if( node.next == null && node.previous == null )
141 {
142 first = last = null;
143 }
144 else if( node.next == null )
145 {
146 node.previous.next = null;
147 last = node.previous;
148 }
149 else if( node.previous == null )
150 {
151 node.next.previous = null;
152 first = node.next;
153 }
154 else
155 {
156 node.previous.next = node.next;
157 node.next.previous = node.previous;
158 }
159
160 }
161
162
163 private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
164 {
165
166 if( pos < 0 )
167 {
168 if( last == null )
169 {
170 last = parentNode;
171 }
172
173 if( parentNode.previous == null )
174 {
175 first = node;
176 }
177 else
178 {
179 parentNode.previous.next = node ;
180 node.previous = parentNode.previous;
181 }
182
183 node.next = parentNode;
184 parentNode.previous = node;
185 }
186 else if( pos > 0 )
187 {
188 if( parentNode.next == null )
189 {
190 last = node;
191 }
192 else
193 {
194 parentNode.next.previous = node;
195 node.next = parentNode.next;
196 }
197 node.previous = parentNode;
198 parentNode.next = node;
199 }
200
201 }
202
203
204
205
206
207
208
209
210 public K remove( K key )
211 {
212 LinkedAvlNode<K> temp = null;
213 LinkedAvlNode<K> y = null;
214
215 List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>();
216
217 treePath = find( key, root, treePath);
218
219 if( treePath == null )
220 {
221 return null;
222 }
223
224 temp = treePath.remove( 0 );
225
226
227 removeFromList(temp);
228
229 if( temp.isLeaf() )
230 {
231 if( temp == root )
232 {
233 root = null;
234 return key;
235 }
236
237 if( !treePath.isEmpty() )
238 {
239 detachNodes( temp, treePath.get( 0 ) );
240 }
241 }
242 else
243 {
244 if( temp.left != null )
245 {
246 List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left );
247 y = leftTreePath.remove( 0 );
248
249 if( leftTreePath.isEmpty() )
250 {
251 detachNodes( y, temp );
252 }
253 else
254 {
255 detachNodes( y, leftTreePath.remove( 0 ) );
256 }
257
258 leftTreePath.addAll( treePath );
259 treePath = leftTreePath;
260
261 y.right = temp.right;
262
263 if( temp == root )
264 {
265 y.left = temp.left;
266 root = y;
267 }
268 else
269 {
270 replaceNode( temp, y, treePath.get( 0 ) );
271 }
272 }
273 else if( temp.right != null )
274 {
275 List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right );
276 y = rightTreePath.remove( 0 );
277
278 if( rightTreePath.isEmpty() )
279 {
280 detachNodes( y, temp );
281 }
282 else
283 {
284 detachNodes( y, rightTreePath.remove( 0 ) );
285 }
286
287 rightTreePath.addAll( treePath );
288 treePath = rightTreePath;
289
290 y.right = temp.right;
291
292 if( temp == root )
293 {
294 y.right = temp.right;
295 root = y;
296 }
297 else
298 {
299 replaceNode( temp, y, treePath.get( 0 ) );
300 }
301 }
302 }
303
304 treePath.add( 0, y );
305 balance( treePath );
306
307 return key;
308 }
309
310
311
312
313
314
315
316
317
318
319
320
321
322 private void balance( List<LinkedAvlNode<K>> treePath )
323 {
324 LinkedAvlNode<K> parentNode = null;
325
326 int size = treePath.size();
327
328 for( LinkedAvlNode<K> node: treePath )
329 {
330 int balFactor = getBalance( node );
331
332 if( node != root )
333 {
334 if( treePath.indexOf( node ) < ( size - 1 ) )
335 {
336 parentNode = treePath.get( treePath.indexOf( node ) + 1 );
337 }
338 }
339
340 if( balFactor > 1 )
341 {
342 if( getBalance( node.right ) <= -1)
343 {
344
345 rotateSingleRight( node.right, node );
346 rotateSingleLeft( node, parentNode );
347 }
348 else
349 {
350 rotateSingleLeft( node, parentNode );
351 }
352 }
353 else if( balFactor < -1 )
354 {
355 if( getBalance( node.left ) >= 1)
356 {
357
358 rotateSingleLeft( node.left, node );
359 rotateSingleRight( node, parentNode );
360 }
361 else
362 {
363 rotateSingleRight( node, parentNode );
364 }
365 }
366 }
367 }
368
369
370
371
372
373
374
375 public boolean isEmpty()
376 {
377 return root == null;
378 }
379
380
381
382
383
384
385
386
387 public int getSize()
388 {
389 if ( root == null )
390 {
391 return 0;
392 }
393
394 if( root.isLeaf() )
395 {
396 return 1;
397 }
398
399 LinkedAvlNode<K> x = first.next;
400
401 while( x != null )
402 {
403 x.setIndex( x.previous.getIndex() + 1 );
404 x = x.next;
405 }
406
407 return last.getIndex() + 1;
408 }
409
410
411
412
413
414
415
416
417
418
419 {
420 this.root = root;
421 }
422
423
424
425
426
427
428
429
430
431
432 {
433 this.first = first;
434 }
435
436
437
438
439
440
441
442
443
444
445 {
446 this.last = last;
447 }
448
449
450
451
452
453
454 public LinkedAvlNode<K> getRoot()
455 {
456 return root;
457 }
458
459
460
461
462
463 public List<K> getKeys()
464 {
465 List<K> keys = new ArrayList<K>();
466 LinkedAvlNode<K> node = first;
467
468 while( node != null )
469 {
470 keys.add( node.key );
471 node = node.next;
472 }
473
474 return keys;
475 }
476
477
478
479
480 public void printTree()
481 {
482 if( isEmpty() )
483 {
484 System.out.println( "Tree is empty" );
485 return;
486 }
487
488 getRoot().setDepth( 0 );
489
490 System.out.println( getRoot() );
491
492 visit( getRoot().getRight(), getRoot() );
493
494 visit( getRoot().getLeft(), getRoot() );
495 }
496
497
498
499
500
501 public LinkedAvlNode<K> getFirst()
502 {
503 return first;
504 }
505
506
507
508
509
510 public LinkedAvlNode<K> getLast()
511 {
512 return last;
513 }
514
515
516
517
518
519
520
521
522 private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
523 {
524 LinkedAvlNode<K> temp;
525
526
527 temp = node.right;
528 node.right = temp.left;
529 temp.left = node;
530
531 if( node == root )
532 {
533 root = temp;
534 }
535 else if( parentNode != null )
536 {
537 if( parentNode.left == node )
538 {
539 parentNode.left = temp;
540 }
541 else if( parentNode.right == node )
542 {
543 parentNode.right = temp;
544 }
545 }
546 }
547
548
549
550
551
552
553
554
555 private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
556 {
557 LinkedAvlNode<K> temp;
558
559
560 temp = node.left;
561 node.left = temp.right;
562 temp.right = node;
563
564 if( node == root )
565 {
566 root = temp;
567 }
568 else if( parentNode != null )
569 {
570 if( parentNode.left == node )
571 {
572 parentNode.left = temp;
573 }
574 else if( parentNode.right == node )
575 {
576 parentNode.right = temp;
577 }
578 }
579
580
581
582
583 else if( root != null )
584 {
585 if( root.left == node )
586 {
587 root.left = temp;
588 }
589
590 }
591 }
592
593
594
595
596
597
598
599
600 private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
601 {
602 if( parentNode != null )
603 {
604 if( node == parentNode.left )
605 {
606 parentNode.left = node.left;
607 }
608 else if( node == parentNode.right )
609 {
610 parentNode.right = node.left;
611 }
612 }
613 }
614
615
616
617
618
619
620
621
622
623
624 private void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode)
625 {
626 if( parentNode != null )
627 {
628 replaceNode.left = deleteNode.left;
629
630 if( deleteNode == parentNode.left )
631 {
632 parentNode.left = replaceNode;
633 }
634 else if( deleteNode == parentNode.right )
635 {
636 parentNode.right = replaceNode;
637 }
638 }
639 }
640
641
642
643
644
645
646
647
648
649
650
651 private List<LinkedAvlNode<K>> find( K key, LinkedAvlNode<K> startNode, List<LinkedAvlNode<K>> path )
652 {
653 int c;
654
655 if( startNode == null )
656 {
657 return null;
658 }
659
660 path.add( 0, startNode );
661 c = comparator.compare( key, startNode.key );
662
663 if( c == 0 )
664 {
665 return path;
666 }
667 else if( c > 0 )
668 {
669 return find( key, startNode.right, path );
670 }
671 else if( c < 0 )
672 {
673 return find( key, startNode.left, path );
674 }
675
676 return null;
677 }
678
679
680
681
682
683
684
685
686
687 public LinkedAvlNode<K> findGreater( K key )
688 {
689 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
690
691 if( result == null )
692 {
693 return null;
694 }
695 else if( comparator.compare( key, result.key ) < 0 )
696 {
697 return result;
698 }
699
700 return result.next;
701 }
702
703
704
705
706
707
708
709
710
711 public LinkedAvlNode<K> findGreaterOrEqual( K key )
712 {
713 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
714
715 if( result == null )
716 {
717 return null;
718 }
719 else if( comparator.compare( key, result.key ) <= 0 )
720 {
721 return result;
722 }
723
724 return result.next;
725 }
726
727
728
729
730
731
732
733
734
735 public LinkedAvlNode<K> findLess( K key )
736 {
737 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
738
739 if( result == null )
740 {
741 return null;
742 }
743 else if( comparator.compare( key, result.key ) > 0 )
744 {
745 return result;
746 }
747
748 return result.previous;
749 }
750
751
752
753
754
755
756
757
758
759 public LinkedAvlNode<K> findLessOrEqual( K key )
760 {
761 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root);
762
763 if( result == null )
764 {
765 return null;
766 }
767 else if( comparator.compare( key, result.key ) >= 0 )
768 {
769 return result;
770 }
771
772 return result.previous;
773 }
774
775
776
777
778
779
780
781 private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent )
782 {
783
784 if( startNode == null )
785 {
786 return parent;
787 }
788
789 int c = comparator.compare( key, startNode.key );
790
791 parent = startNode;
792
793 if( c > 0 )
794 {
795 return fetchNonNullNode( key, startNode.right, parent );
796 }
797 else if( c < 0 )
798 {
799 return fetchNonNullNode( key, startNode.left, parent );
800 }
801
802 return startNode;
803 }
804
805
806
807
808
809
810
811
812 public LinkedAvlNode<K> find( K key )
813 {
814 return find( key, root);
815 }
816
817
818 private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode)
819 {
820 int c;
821
822 if( startNode == null )
823 {
824 return null;
825 }
826
827 c = comparator.compare( key, startNode.key );
828
829 if( c > 0 )
830 {
831 startNode.isLeft = false;
832 return find( key, startNode.right );
833 }
834 else if( c < 0 )
835 {
836 startNode.isLeft = true;
837 return find( key, startNode.left );
838 }
839
840 return startNode;
841 }
842
843
844
845
846
847
848
849
850 private List<LinkedAvlNode<K>> findMax( LinkedAvlNode<K> startNode )
851 {
852 LinkedAvlNode<K> x = startNode;
853 LinkedAvlNode<K> y = null;
854 List<LinkedAvlNode<K>> path;
855
856 if( x == null )
857 {
858 return null;
859 }
860
861 while( x.right != null )
862 {
863 x.isLeft = false;
864 y = x;
865 x = x.right;
866 }
867
868 path = new ArrayList<LinkedAvlNode<K>>(2);
869 path.add( x );
870
871 if ( y != null )
872 {
873 path.add( y );
874 }
875
876 return path;
877 }
878
879
880
881
882
883
884
885
886 private List<LinkedAvlNode<K>> findMin( LinkedAvlNode<K> startNode )
887 {
888 LinkedAvlNode<K> x = startNode;
889 LinkedAvlNode<K> y = null;
890 List<LinkedAvlNode<K>> path;
891
892 if( x == null )
893 {
894 return null;
895 }
896
897 while( x.left != null )
898 {
899 x.isLeft = true;
900 y = x;
901 x = x.left;
902 }
903
904 path = new ArrayList<LinkedAvlNode<K>>(2);
905 path.add( x );
906
907 if ( y != null )
908 {
909 path.add( y );
910 }
911
912 return path;
913 }
914
915
916
917
918
919
920
921
922 private int getBalance( LinkedAvlNode<K> node )
923 {
924 if( node == null)
925 {
926 return 0;
927 }
928
929 return node.getBalance();
930 }
931
932
933 private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode )
934 {
935 if( node == null )
936 {
937 return;
938 }
939
940 if( !node.isLeaf() )
941 {
942 node.setDepth( parentNode.getDepth() + 1 );
943 }
944
945 for( int i=0; i < parentNode.getDepth(); i++ )
946 {
947 System.out.print( "| " );
948 }
949
950 String type = "";
951 if( node == parentNode.left )
952 {
953 type = "L";
954 }
955 else if( node == parentNode.right )
956 {
957 type = "R";
958 }
959
960 System.out.println( "|--" + node + type );
961
962 if ( node.getRight() != null )
963 {
964 visit( node.getRight(), node );
965 }
966
967 if( node.getLeft() != null )
968 {
969 visit( node.getLeft(), node );
970 }
971 }
972 }