View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
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   * An AVL tree implementation
30   *
31   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
32   * @version $Rev$, $Date$
33   */
34  public class AvlTree<K>
35  {
36      /** the root of the tree */
37  	private LinkedAvlNode<K> root;
38  
39  	/** The Comparator used for comparing the keys */
40  	private Comparator<K> comparator;
41  
42  	/** node representing the start of the doubly linked list formed with the tree nodes */
43  	private LinkedAvlNode<K> first;
44  	
45  	/** node representing the end of the doubly linked list formed with the tree nodes */
46      private LinkedAvlNode<K> last;
47  
48  
49      /**
50  	 * Creates a new instance of AVLTree.
51  	 *
52  	 * @param comparator the comparator to be used for comparing keys
53  	 */
54  	public AvlTree( Comparator<K> comparator)
55  	{
56  	    this.comparator = comparator;
57  	}
58  	
59  	
60  	/**
61  	 * @return the comparator associated with this tree 
62  	 */
63  	public Comparator<K> getComparator()
64  	{
65  	    return comparator;
66  	}
67  	
68  	
69  	/**
70  	 * Inserts a LinkedAvlNode with the given key.
71  	 *
72  	 * @param key the item to be inserted
73  	 * @return the replaced key if it already exists
74  	 * Note: Ignores if a node with the given key already exists.
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 ); // last node first, for the sake of balance factor computation
99  	        parent = temp;
100 	        
101 	        c = comparator.compare( key, temp.getKey() );
102 	        
103 	        if( c == 0 )
104 	        {
105 	            return key; // key already exists
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 ) // should happen in case of tree having single node
141         {
142             first = last = null;
143         }
144         else if( node.next == null ) // last node
145         {
146             node.previous.next = null;
147             last = node.previous;
148         }
149         else if( node.previous == null ) // first node
150         {
151             node.next.previous = null;
152             first = node.next;
153         }
154         else // somewhere in middle
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      * Removes the LinkedAvlNode present in the tree with the given key value
206      *
207      * @param key the value of the node to be removed
208      * @return the removed key, if any, or null if the key does not exist
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         // remove from the doubly linked
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() ) // y is the left child of root and y is a leaf
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; // assign the right here left will be assigned in replaceNode()
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 ); // y is the right child of root and y is a leaf
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; // assign the right here left will be assigned in replaceNode()
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 ); // y can be null but getBalance returns 0 so np
305        balance( treePath );
306        
307        return key;
308     }
309     
310     
311 	/**
312 	 * Balances the tree by visiting the nodes present in the List of nodes present in the
313 	 * treePath parameter.<br><br>
314 	 *
315 	 * This really does the balancing if the height of the tree is greater than 2 and the<br> 
316 	 * balance factor is greater than +1 or less than -1.<br><br>
317 	 * For an excellent info please read the 
318 	 * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>.
319 	 * 
320 	 * @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete operation.
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 	                //------rotate double-left--------
345 	                rotateSingleRight( node.right, node );
346 	                rotateSingleLeft( node, parentNode );
347 	            }
348 	            else // rotate single-left
349 	            {
350 	               rotateSingleLeft( node, parentNode );
351 	            }
352 	        }
353 	        else if( balFactor < -1 )
354 	        {
355 	            if( getBalance( node.left ) >= 1)
356 	            {
357 	               //------rotate double-right--------
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      * Tests if the tree is logically empty.
372      * 
373      * @return true if the tree is empty, false otherwise
374      */
375     public boolean isEmpty()
376     {
377       return root == null;   
378     }
379 
380     
381     /**
382      * returns the number of nodes present in this tree.
383      * 
384      * @return the number of nodes present in this tree
385      */
386     //NOTE: This method is internally used by AVLTreeMarshaller
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      * Set the root of the tree.
413      * 
414      * Note : this method is used by the deserialization method
415      *
416      * @param root the root of the tree
417      */
418     /* no protection */ void setRoot( LinkedAvlNode<K> root )
419     {
420         this.root = root;
421     }
422 
423     
424     /**
425      * Set the first element of the tree
426      * 
427      * Note : this method is used by the deserialization method
428      *
429      * @param first the first element to be added
430      */
431     /* no protection */  void setFirst( LinkedAvlNode<K> first )
432     {
433         this.first = first;
434     }
435 
436     
437     /**
438      * Set the last element of the tree
439      * 
440      * Note : this method is used by the deserialization method
441      *
442      * @param last the last element to be added
443      */
444     /* no protection */  void setLast( LinkedAvlNode<K> last )
445     {
446         this.last = last;
447     }
448 
449 
450     /**
451      * @return the root element of this tree (ie, not the first, but the
452      * topmost element)
453      */
454     public LinkedAvlNode<K> getRoot()
455     {
456         return root;
457     }
458     
459     
460     /**
461      * @return a list of the stored keys in this tree
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      * Prints the contents of AVL tree in pretty format
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      * @return The first element of this tree
500      */
501 	public LinkedAvlNode<K> getFirst()
502     {
503         return first;
504     }
505 
506 	
507 	/**
508 	 * @return The last element in this tree
509 	 */
510     public LinkedAvlNode<K> getLast()
511     {
512         return last;
513     }
514 
515     
516     /**
517 	 * Rotate the node left side once.
518 	 *
519 	 * @param node the LinkedAvlNode to be rotated
520 	 * @param parentNode parent LinkedAvlNode of node
521 	 */
522 	private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
523 	{
524 	    LinkedAvlNode<K> temp;
525 	    //------rotate single-left--------
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      * Rotate the node right side once.
551      *
552      * @param node the LinkedAvlNode to be rotated
553      * @param parentNode parent LinkedAvlNode of node
554      */
555 	private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
556 	{
557 	    LinkedAvlNode<K> temp;
558         //------rotate single-right--------
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          when the 'parentNode' param is null then the node under rotation is a child of ROOT.
581          Most likely this condition executes when the root node is deleted and balancing is required.
582          */
583         else if( root != null )
584         {
585             if( root.left == node )
586             {
587                 root.left = temp;
588             }
589             // no need to check for right node
590         }
591 	}
592 		
593 
594 	/**
595 	 * Detach a LinkedAvlNode from its parent
596 	 *
597 	 * @param node the LinkedAvlNode to be detached
598 	 * @param parentNode the parent LinkedAvlNode of the node
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 	 * Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode 
619 	 *
620 	 * @param deleteNode the LinkedAvlNode to be deleted
621 	 * @param replaceNode the LinkedAvlNode to replace the deleteNode
622 	 * @param parentNode the parent LinkedAvlNode of deleteNode
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      * Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
645      *
646      * @param key the key to find
647      * @param startNode starting node of a subtree/tree
648      * @param path the list to be filled with traversed nodes
649      * @return the list of traversed LinkedAvlNodes.
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      * Finds a LinkedAvlNode<K> whose key is higher than the given key.
682      *
683      * @param key the key
684      * @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
685      *         null if there is no node with a higher key than the given key.
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      * Finds a LinkedAvlNode<K> whose key is higher than the given key.
706      *
707      * @param key the key
708      * @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
709      *         null if there is no node with a higher key than the given key.
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      * Finds a LinkedAvlNode<K> whose key is lower than the given key.
730      *
731      * @param key the key
732      * @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
733      *         null if there is no node with a lower key than the given key.
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      * Finds a LinkedAvlNode<K> whose key is lower than the given key.
754      *
755      * @param key the key
756      * @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
757      *         null if there is no node with a lower key than the given key.
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      * This method returns the last visited non-null node in case if the node with the given key
778      * is not present. This method should not be used as general purpose lookup method.
779      * This is written to assist the findGreater, findLess methods. 
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      * Find a LinkedAvlNode with the given key value in the tree.
808      *
809      * @param key the key to find
810      * @return the list of traversed LinkedAvlNode.
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      * Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
846      *
847      * @param startNode starting node of a subtree/tree
848      * @return the list of traversed LinkedAvlNodes.
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      * Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
882      *
883      * @param startNode starting node of a subtree/tree
884      * @return the list of traversed LinkedAvlNodes.
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      * Get balance-factor of the given LinkedAvlNode.
918      *
919      * @param node a LinkedAvlNode 
920      * @return balance-factor of the node
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 }