001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.core.avltree; 021 022 023 import java.util.ArrayList; 024 import java.util.Comparator; 025 import java.util.List; 026 027 028 /** 029 * An AVL tree implementation 030 * 031 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 032 * @version $Rev$, $Date$ 033 */ 034 public class AvlTreeImpl<K> implements AvlTree<K> 035 { 036 /** the root of the tree */ 037 private LinkedAvlNode<K> root; 038 039 /** The Comparator used for comparing the keys */ 040 private Comparator<K> comparator; 041 042 /** node representing the start of the doubly linked list formed with the tree nodes */ 043 private LinkedAvlNode<K> first; 044 045 /** node representing the end of the doubly linked list formed with the tree nodes */ 046 private LinkedAvlNode<K> last; 047 048 /** size of the tree */ 049 private int size; 050 051 /** 052 * Creates a new instance of AVLTree. 053 * 054 * @param comparator the comparator to be used for comparing keys 055 */ 056 public AvlTreeImpl( Comparator<K> comparator) 057 { 058 this.comparator = comparator; 059 } 060 061 062 /* (non-Javadoc) 063 * @see org.apache.directory.server.core.avltree.AvlTree#getComparator() 064 */ 065 public Comparator<K> getComparator() 066 { 067 return comparator; 068 } 069 070 071 /* (non-Javadoc) 072 * @see org.apache.directory.server.core.avltree.AvlTree#insert(K) 073 */ 074 public K insert( K key ) 075 { 076 LinkedAvlNode<K> node, temp; 077 LinkedAvlNode<K> parent = null; 078 int c; 079 080 if ( root == null ) 081 { 082 root = new LinkedAvlNode<K>( key ); 083 first = root; 084 last = root; 085 size++; 086 return null; 087 } 088 089 node = new LinkedAvlNode<K>( key ); 090 091 temp = root; 092 093 List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>(); 094 095 while( temp != null ) 096 { 097 treePath.add(0, temp ); // last node first, for the sake of balance factor computation 098 parent = temp; 099 100 c = comparator.compare( key, temp.getKey() ); 101 102 if( c == 0 ) 103 { 104 return key; // key already exists 105 } 106 107 if( c < 0 ) 108 { 109 temp.isLeft = true; 110 temp = temp.getLeft(); 111 } 112 else 113 { 114 temp.isLeft = false; 115 temp = temp.getRight(); 116 } 117 } 118 119 if( ( c = comparator.compare( key, parent.getKey() ) ) < 0 ) 120 { 121 parent.setLeft( node ); 122 } 123 else 124 { 125 parent.setRight( node ); 126 } 127 128 insertInList( node, parent, c ); 129 130 treePath.add( 0, node ); 131 balance(treePath); 132 133 size++; 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 /* (non-Javadoc) 205 * @see org.apache.directory.server.core.avltree.AvlTree#remove(K) 206 */ 207 public K remove( K key ) 208 { 209 LinkedAvlNode<K> temp = null; 210 LinkedAvlNode<K> y = null; 211 212 List<LinkedAvlNode<K>> treePath = new ArrayList<LinkedAvlNode<K>>(); 213 214 treePath = find( key, root, treePath); 215 216 if( treePath == null ) 217 { 218 return null; 219 } 220 221 temp = treePath.remove( 0 ); 222 223 // remove from the doubly linked 224 removeFromList(temp); 225 226 if( temp.isLeaf() ) 227 { 228 if( temp == root ) 229 { 230 root = null; 231 size--; 232 return key; 233 } 234 235 if( !treePath.isEmpty() ) 236 { 237 detachNodes( temp, treePath.get( 0 ) ); 238 } 239 } 240 else 241 { 242 if( temp.left != null ) 243 { 244 List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left ); 245 y = leftTreePath.remove( 0 ); 246 247 if( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf 248 { 249 detachNodes( y, temp ); 250 } 251 else 252 { 253 detachNodes( y, leftTreePath.remove( 0 ) ); 254 } 255 256 leftTreePath.addAll( treePath ); 257 treePath = leftTreePath; 258 259 y.right = temp.right; // assign the right here left will be assigned in replaceNode() 260 261 if( temp == root ) 262 { 263 y.left = temp.left; 264 root = y; 265 } 266 else 267 { 268 replaceNode( temp, y, treePath.get( 0 ) ); 269 } 270 } 271 else if( temp.right != null ) 272 { 273 List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right ); 274 y = rightTreePath.remove( 0 ); 275 276 if( rightTreePath.isEmpty() ) 277 { 278 detachNodes( y, temp ); // y is the right child of root and y is a leaf 279 } 280 else 281 { 282 detachNodes( y, rightTreePath.remove( 0 ) ); 283 } 284 285 rightTreePath.addAll( treePath ); 286 treePath = rightTreePath; 287 288 y.right = temp.right; // assign the right here left will be assigned in replaceNode() 289 290 if( temp == root ) 291 { 292 y.right = temp.right; 293 root = y; 294 } 295 else 296 { 297 replaceNode( temp, y, treePath.get( 0 ) ); 298 } 299 } 300 } 301 302 treePath.add( 0, y ); // y can be null but getBalance returns 0 so np 303 balance( treePath ); 304 305 size--; 306 return key; 307 } 308 309 310 /** 311 * Balances the tree by visiting the nodes present in the List of nodes present in the 312 * treePath parameter.<br><br> 313 * 314 * This really does the balancing if the height of the tree is greater than 2 and the<br> 315 * balance factor is greater than +1 or less than -1.<br><br> 316 * For an excellent info please read the 317 * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>. 318 * 319 * @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete operation. 320 */ 321 private void balance( List<LinkedAvlNode<K>> treePath ) 322 { 323 LinkedAvlNode<K> parentNode = null; 324 325 int size = treePath.size(); 326 327 for( LinkedAvlNode<K> node: treePath ) 328 { 329 int balFactor = getBalance( node ); 330 331 if( node != root ) 332 { 333 if( treePath.indexOf( node ) < ( size - 1 ) ) 334 { 335 parentNode = treePath.get( treePath.indexOf( node ) + 1 ); 336 } 337 } 338 339 if( balFactor > 1 ) 340 { 341 if( getBalance( node.right ) <= -1) 342 { 343 //------rotate double-left-------- 344 rotateSingleRight( node.right, node ); 345 rotateSingleLeft( node, parentNode ); 346 } 347 else // rotate single-left 348 { 349 rotateSingleLeft( node, parentNode ); 350 } 351 } 352 else if( balFactor < -1 ) 353 { 354 if( getBalance( node.left ) >= 1) 355 { 356 //------rotate double-right-------- 357 rotateSingleLeft( node.left, node ); 358 rotateSingleRight( node, parentNode ); 359 } 360 else 361 { 362 rotateSingleRight( node, parentNode ); 363 } 364 } 365 } 366 } 367 368 369 /* (non-Javadoc) 370 * @see org.apache.directory.server.core.avltree.AvlTree#isEmpty() 371 */ 372 public boolean isEmpty() 373 { 374 return root == null; 375 } 376 377 378 /* (non-Javadoc) 379 * @see org.apache.directory.server.core.avltree.AvlTree#getSize() 380 */ 381 //NOTE: This method is internally used by AVLTreeMarshaller 382 public int getSize() 383 { 384 return size; 385 } 386 387 /** 388 * Set the size of the tree. 389 * 390 * Note : this method is used by the deserialization method 391 * 392 * @param size the size of the tree 393 */ 394 /* no protection */ void setSize( int size ) 395 { 396 this.size = size; 397 } 398 399 400 /** 401 * Set the root of the tree. 402 * 403 * Note : this method is used by the deserialization method 404 * 405 * @param root the root of the tree 406 */ 407 /* no protection */ void setRoot( LinkedAvlNode<K> root ) 408 { 409 this.root = root; 410 } 411 412 413 /** 414 * Set the first element of the tree 415 * 416 * Note : this method is used by the deserialization method 417 * 418 * @param first the first element to be added 419 */ 420 /* no protection */ void setFirst( LinkedAvlNode<K> first ) 421 { 422 this.first = first; 423 size++; 424 } 425 426 427 /** 428 * Set the last element of the tree 429 * 430 * Note : this method is used by the deserialization method 431 * 432 * @param last the last element to be added 433 */ 434 /* no protection */ void setLast( LinkedAvlNode<K> last ) 435 { 436 this.last = last; 437 } 438 439 440 /* (non-Javadoc) 441 * @see org.apache.directory.server.core.avltree.AvlTree#getRoot() 442 */ 443 public LinkedAvlNode<K> getRoot() 444 { 445 return root; 446 } 447 448 449 /* (non-Javadoc) 450 * @see org.apache.directory.server.core.avltree.AvlTree#getKeys() 451 */ 452 public List<K> getKeys() 453 { 454 List<K> keys = new ArrayList<K>(); 455 LinkedAvlNode<K> node = first; 456 457 while( node != null ) 458 { 459 keys.add( node.key ); 460 node = node.next; 461 } 462 463 return keys; 464 } 465 466 /* (non-Javadoc) 467 * @see org.apache.directory.server.core.avltree.AvlTree#printTree() 468 */ 469 public void printTree() 470 { 471 if( isEmpty() ) 472 { 473 System.out.println( "Tree is empty" ); 474 return; 475 } 476 477 getRoot().setDepth( 0 ); 478 479 System.out.println( getRoot() ); 480 481 visit( getRoot().getRight(), getRoot() ); 482 483 visit( getRoot().getLeft(), getRoot() ); 484 } 485 486 487 /* (non-Javadoc) 488 * @see org.apache.directory.server.core.avltree.AvlTree#getFirst() 489 */ 490 public LinkedAvlNode<K> getFirst() 491 { 492 return first; 493 } 494 495 496 /* (non-Javadoc) 497 * @see org.apache.directory.server.core.avltree.AvlTree#getLast() 498 */ 499 public LinkedAvlNode<K> getLast() 500 { 501 return last; 502 } 503 504 505 /** 506 * Rotate the node left side once. 507 * 508 * @param node the LinkedAvlNode to be rotated 509 * @param parentNode parent LinkedAvlNode of node 510 */ 511 private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) 512 { 513 LinkedAvlNode<K> temp; 514 //------rotate single-left-------- 515 516 temp = node.right; 517 node.right = temp.left; 518 temp.left = node; 519 520 if( node == root ) 521 { 522 root = temp; 523 } 524 else if( parentNode != null ) 525 { 526 if( parentNode.left == node ) 527 { 528 parentNode.left = temp; 529 } 530 else if( parentNode.right == node ) 531 { 532 parentNode.right = temp; 533 } 534 } 535 } 536 537 538 /** 539 * Rotate the node right side once. 540 * 541 * @param node the LinkedAvlNode to be rotated 542 * @param parentNode parent LinkedAvlNode of node 543 */ 544 private void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) 545 { 546 LinkedAvlNode<K> temp; 547 //------rotate single-right-------- 548 549 temp = node.left; 550 node.left = temp.right; 551 temp.right = node; 552 553 if( node == root ) 554 { 555 root = temp; 556 } 557 else if( parentNode != null ) 558 { 559 if( parentNode.left == node ) 560 { 561 parentNode.left = temp; 562 } 563 else if( parentNode.right == node ) 564 { 565 parentNode.right = temp; 566 } 567 } 568 /* 569 when the 'parentNode' param is null then the node under rotation is a child of ROOT. 570 Most likely this condition executes when the root node is deleted and balancing is required. 571 */ 572 else if( root != null ) 573 { 574 if( root.left == node ) 575 { 576 root.left = temp; 577 } 578 // no need to check for right node 579 } 580 } 581 582 583 /** 584 * Detach a LinkedAvlNode from its parent 585 * 586 * @param node the LinkedAvlNode to be detached 587 * @param parentNode the parent LinkedAvlNode of the node 588 */ 589 private void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) 590 { 591 if( parentNode != null ) 592 { 593 if( node == parentNode.left ) 594 { 595 parentNode.left = node.left; 596 } 597 else if( node == parentNode.right ) 598 { 599 parentNode.right = node.left; 600 } 601 } 602 } 603 604 605 /** 606 * 607 * Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode 608 * 609 * @param deleteNode the LinkedAvlNode to be deleted 610 * @param replaceNode the LinkedAvlNode to replace the deleteNode 611 * @param parentNode the parent LinkedAvlNode of deleteNode 612 */ 613 private void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode) 614 { 615 if( parentNode != null ) 616 { 617 replaceNode.left = deleteNode.left; 618 619 if( deleteNode == parentNode.left ) 620 { 621 parentNode.left = replaceNode; 622 } 623 else if( deleteNode == parentNode.right ) 624 { 625 parentNode.right = replaceNode; 626 } 627 } 628 } 629 630 631 /** 632 * 633 * Find a LinkedAvlNode with the given key value in the tree starting from the startNode. 634 * 635 * @param key the key to find 636 * @param startNode starting node of a subtree/tree 637 * @param path the list to be filled with traversed nodes 638 * @return the list of traversed LinkedAvlNodes. 639 */ 640 private List<LinkedAvlNode<K>> find( K key, LinkedAvlNode<K> startNode, List<LinkedAvlNode<K>> path ) 641 { 642 int c; 643 644 if( startNode == null ) 645 { 646 return null; 647 } 648 649 path.add( 0, startNode ); 650 c = comparator.compare( key, startNode.key ); 651 652 if( c == 0 ) 653 { 654 return path; 655 } 656 else if( c > 0 ) 657 { 658 return find( key, startNode.right, path ); 659 } 660 else if( c < 0 ) 661 { 662 return find( key, startNode.left, path ); 663 } 664 665 return null; 666 } 667 668 669 /* (non-Javadoc) 670 * @see org.apache.directory.server.core.avltree.AvlTree#findGreater(K) 671 */ 672 public LinkedAvlNode<K> findGreater( K key ) 673 { 674 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root); 675 676 if( result == null ) 677 { 678 return null; 679 } 680 else if( comparator.compare( key, result.key ) < 0 ) 681 { 682 return result; 683 } 684 685 return result.next; 686 } 687 688 689 /* (non-Javadoc) 690 * @see org.apache.directory.server.core.avltree.AvlTree#findGreaterOrEqual(K) 691 */ 692 public LinkedAvlNode<K> findGreaterOrEqual( K key ) 693 { 694 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root); 695 696 if( result == null ) 697 { 698 return null; 699 } 700 else if( comparator.compare( key, result.key ) <= 0 ) 701 { 702 return result; 703 } 704 705 return result.next; 706 } 707 708 709 /* (non-Javadoc) 710 * @see org.apache.directory.server.core.avltree.AvlTree#findLess(K) 711 */ 712 public LinkedAvlNode<K> findLess( K key ) 713 { 714 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root); 715 716 if( result == null ) 717 { 718 return null; 719 } 720 else if( comparator.compare( key, result.key ) > 0 ) 721 { 722 return result; 723 } 724 725 return result.previous; 726 } 727 728 729 /* (non-Javadoc) 730 * @see org.apache.directory.server.core.avltree.AvlTree#findLessOrEqual(K) 731 */ 732 public LinkedAvlNode<K> findLessOrEqual( K key ) 733 { 734 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root); 735 736 if( result == null ) 737 { 738 return null; 739 } 740 else if( comparator.compare( key, result.key ) >= 0 ) 741 { 742 return result; 743 } 744 745 return result.previous; 746 } 747 748 749 /* 750 * This method returns the last visited non-null node in case if the node with the given key 751 * is not present. This method should not be used as general purpose lookup method. 752 * This is written to assist the findGreater, findLess methods. 753 */ 754 private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent ) 755 { 756 757 if( startNode == null ) 758 { 759 return parent; 760 } 761 762 int c = comparator.compare( key, startNode.key ); 763 764 parent = startNode; 765 766 if( c > 0 ) 767 { 768 return fetchNonNullNode( key, startNode.right, parent ); 769 } 770 else if( c < 0 ) 771 { 772 return fetchNonNullNode( key, startNode.left, parent ); 773 } 774 775 return startNode; 776 } 777 778 /* (non-Javadoc) 779 * @see org.apache.directory.server.core.avltree.AvlTree#find(K) 780 */ 781 public LinkedAvlNode<K> find( K key ) 782 { 783 return find( key, root); 784 } 785 786 787 private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode) 788 { 789 int c; 790 791 if( startNode == null ) 792 { 793 return null; 794 } 795 796 c = comparator.compare( key, startNode.key ); 797 798 if( c > 0 ) 799 { 800 startNode.isLeft = false; 801 return find( key, startNode.right ); 802 } 803 else if( c < 0 ) 804 { 805 startNode.isLeft = true; 806 return find( key, startNode.left ); 807 } 808 809 return startNode; 810 } 811 812 813 /** 814 * Find the LinkedAvlNode having the max key value in the tree starting from the startNode. 815 * 816 * @param startNode starting node of a subtree/tree 817 * @return the list of traversed LinkedAvlNodes. 818 */ 819 private List<LinkedAvlNode<K>> findMax( LinkedAvlNode<K> startNode ) 820 { 821 LinkedAvlNode<K> x = startNode; 822 LinkedAvlNode<K> y = null; 823 List<LinkedAvlNode<K>> path; 824 825 if( x == null ) 826 { 827 return null; 828 } 829 830 while( x.right != null ) 831 { 832 x.isLeft = false; 833 y = x; 834 x = x.right; 835 } 836 837 path = new ArrayList<LinkedAvlNode<K>>(2); 838 path.add( x ); 839 840 if ( y != null ) 841 { 842 path.add( y ); 843 } 844 845 return path; 846 } 847 848 849 /** 850 * Find the LinkedAvlNode having the min key value in the tree starting from the startNode. 851 * 852 * @param startNode starting node of a subtree/tree 853 * @return the list of traversed LinkedAvlNodes. 854 */ 855 private List<LinkedAvlNode<K>> findMin( LinkedAvlNode<K> startNode ) 856 { 857 LinkedAvlNode<K> x = startNode; 858 LinkedAvlNode<K> y = null; 859 List<LinkedAvlNode<K>> path; 860 861 if( x == null ) 862 { 863 return null; 864 } 865 866 while( x.left != null ) 867 { 868 x.isLeft = true; 869 y = x; 870 x = x.left; 871 } 872 873 path = new ArrayList<LinkedAvlNode<K>>(2); 874 path.add( x ); 875 876 if ( y != null ) 877 { 878 path.add( y ); 879 } 880 881 return path; 882 } 883 884 885 /** 886 * Get balance-factor of the given LinkedAvlNode. 887 * 888 * @param node a LinkedAvlNode 889 * @return balance-factor of the node 890 */ 891 private int getBalance( LinkedAvlNode<K> node ) 892 { 893 if( node == null) 894 { 895 return 0; 896 } 897 898 return node.getBalance(); 899 } 900 901 902 private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode ) 903 { 904 if( node == null ) 905 { 906 return; 907 } 908 909 if( !node.isLeaf() ) 910 { 911 node.setDepth( parentNode.getDepth() + 1 ); 912 } 913 914 for( int i=0; i < parentNode.getDepth(); i++ ) 915 { 916 System.out.print( "| " ); 917 } 918 919 String type = ""; 920 if( node == parentNode.left ) 921 { 922 type = "L"; 923 } 924 else if( node == parentNode.right ) 925 { 926 type = "R"; 927 } 928 929 System.out.println( "|--" + node + type ); 930 931 if ( node.getRight() != null ) 932 { 933 visit( node.getRight(), node ); 934 } 935 936 if( node.getLeft() != null ) 937 { 938 visit( node.getLeft(), node ); 939 } 940 } 941 }