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 */ 020package org.apache.directory.server.core.avltree; 021 022 023import java.util.ArrayList; 024import java.util.Comparator; 025import 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 */ 033public class AvlTreeImpl<K> implements AvlTree<K> 034{ 035 /** the root of the tree */ 036 private LinkedAvlNode<K> root; 037 038 /** The Comparator used for comparing the keys */ 039 private Comparator<K> comparator; 040 041 /** node representing the start of the doubly linked list formed with the tree nodes */ 042 private LinkedAvlNode<K> first; 043 044 /** node representing the end of the doubly linked list formed with the tree nodes */ 045 private LinkedAvlNode<K> last; 046 047 /** size of the tree */ 048 private int size; 049 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<>( key ); 083 first = root; 084 last = root; 085 size++; 086 return null; 087 } 088 089 node = new LinkedAvlNode<>( key ); 090 091 temp = root; 092 093 List<LinkedAvlNode<K>> treePath = new ArrayList<>(); 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 c = comparator.compare( key, parent.getKey() ); 120 if ( c < 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 size++; 135 return null; 136 } 137 138 139 private void removeFromList( LinkedAvlNode<K> node ) 140 { 141 if ( node.next == null && node.previous == null ) // should happen in case of tree having single node 142 { 143 first = null; 144 last = null; 145 } 146 else if ( node.next == null ) // last node 147 { 148 node.previous.next = null; 149 last = node.previous; 150 } 151 else if ( node.previous == null ) // first node 152 { 153 node.next.previous = null; 154 first = node.next; 155 } 156 else 157 // somewhere in middle 158 { 159 node.previous.next = node.next; 160 node.next.previous = node.previous; 161 } 162 163 } 164 165 166 private void insertInList( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos ) 167 { 168 169 if ( pos < 0 ) 170 { 171 if ( last == null ) 172 { 173 last = parentNode; 174 } 175 176 if ( parentNode.previous == null ) 177 { 178 first = node; 179 } 180 else 181 { 182 parentNode.previous.next = node; 183 node.previous = parentNode.previous; 184 } 185 186 node.next = parentNode; 187 parentNode.previous = node; 188 } 189 else if ( pos > 0 ) 190 { 191 if ( parentNode.next == null ) 192 { 193 last = node; 194 } 195 else 196 { 197 parentNode.next.previous = node; 198 node.next = parentNode.next; 199 } 200 node.previous = parentNode; 201 parentNode.next = node; 202 } 203 204 } 205 206 207 /* (non-Javadoc) 208 * @see org.apache.directory.server.core.avltree.AvlTree#remove(K) 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<>(); 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 size--; 235 return key; 236 } 237 238 if ( !treePath.isEmpty() ) 239 { 240 detachNodes( temp, treePath.get( 0 ) ); 241 } 242 } 243 else 244 { 245 if ( temp.left != null ) 246 { 247 List<LinkedAvlNode<K>> leftTreePath = findMax( temp.left ); 248 y = leftTreePath.remove( 0 ); 249 250 if ( leftTreePath.isEmpty() ) // y is the left child of root and y is a leaf 251 { 252 detachNodes( y, temp ); 253 } 254 else 255 { 256 detachNodes( y, leftTreePath.remove( 0 ) ); 257 } 258 259 leftTreePath.addAll( treePath ); 260 treePath = leftTreePath; 261 262 y.right = temp.right; // assign the right here left will be assigned in replaceNode() 263 264 if ( temp == root ) 265 { 266 y.left = temp.left; 267 root = y; 268 } 269 else 270 { 271 replaceNode( temp, y, treePath.get( 0 ) ); 272 } 273 } 274 else if ( temp.right != null ) 275 { 276 List<LinkedAvlNode<K>> rightTreePath = findMin( temp.right ); 277 y = rightTreePath.remove( 0 ); 278 279 if ( rightTreePath.isEmpty() ) 280 { 281 detachNodes( y, temp ); // y is the right child of root and y is a leaf 282 } 283 else 284 { 285 detachNodes( y, rightTreePath.remove( 0 ) ); 286 } 287 288 rightTreePath.addAll( treePath ); 289 treePath = rightTreePath; 290 291 y.right = temp.right; // assign the right here left will be assigned in replaceNode() 292 293 if ( temp == root ) 294 { 295 y.right = temp.right; 296 root = y; 297 } 298 else 299 { 300 replaceNode( temp, y, treePath.get( 0 ) ); 301 } 302 } 303 } 304 305 treePath.add( 0, y ); // y can be null but getBalance returns 0 so np 306 balance( treePath ); 307 308 size--; 309 return key; 310 } 311 312 313 /** 314 * Balances the tree by visiting the nodes present in the List of nodes present in the 315 * treePath parameter.<br><br> 316 * 317 * This really does the balancing if the height of the tree is greater than 2 and the<br> 318 * balance factor is greater than +1 or less than -1.<br><br> 319 * For an excellent info please read the 320 * <a href="http://en.wikipedia.org/wiki/Avl_tree">Wikipedia article on AVL tree</a>. 321 * 322 * @param treePath the traversed list of LinkedAvlNodes after performing an insert/delete operation. 323 */ 324 private void balance( List<LinkedAvlNode<K>> treePath ) 325 { 326 LinkedAvlNode<K> parentNode = null; 327 328 int treePathSize = treePath.size(); 329 330 for ( LinkedAvlNode<K> node : treePath ) 331 { 332 int balFactor = getBalance( node ); 333 334 if ( node != root && treePath.indexOf( node ) < ( treePathSize - 1 ) ) 335 { 336 parentNode = treePath.get( treePath.indexOf( node ) + 1 ); 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 348 // 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 /* (non-Javadoc) 371 * @see org.apache.directory.server.core.avltree.AvlTree#isEmpty() 372 */ 373 public boolean isEmpty() 374 { 375 return root == null; 376 } 377 378 379 /* (non-Javadoc) 380 * @see org.apache.directory.server.core.avltree.AvlTree#getSize() 381 */ 382 //NOTE: This method is internally used by AVLTreeMarshaller 383 public int getSize() 384 { 385 return size; 386 } 387 388 389 /** 390 * Set the size of the tree. 391 * 392 * Note : this method is used by the deserialization method 393 * 394 * @param size the size of the tree 395 */ 396 /* no protection */void setSize( int size ) 397 { 398 this.size = size; 399 } 400 401 402 /** 403 * Set the root of the tree. 404 * 405 * Note : this method is used by the deserialization method 406 * 407 * @param root the root of the tree 408 */ 409 /* no protection */void setRoot( LinkedAvlNode<K> root ) 410 { 411 this.root = root; 412 } 413 414 415 /** 416 * Set the first element of the tree 417 * 418 * Note : this method is used by the deserialization method 419 * 420 * @param first the first element to be added 421 */ 422 /* no protection */void setFirst( LinkedAvlNode<K> first ) 423 { 424 this.first = first; 425 size++; 426 } 427 428 429 /** 430 * Set the last element of the tree 431 * 432 * Note : this method is used by the deserialization method 433 * 434 * @param last the last element to be added 435 */ 436 /* no protection */void setLast( LinkedAvlNode<K> last ) 437 { 438 this.last = last; 439 } 440 441 442 /* (non-Javadoc) 443 * @see org.apache.directory.server.core.avltree.AvlTree#getRoot() 444 */ 445 public LinkedAvlNode<K> getRoot() 446 { 447 return root; 448 } 449 450 451 /* (non-Javadoc) 452 * @see org.apache.directory.server.core.avltree.AvlTree#getKeys() 453 */ 454 public List<K> getKeys() 455 { 456 List<K> keys = new ArrayList<>(); 457 LinkedAvlNode<K> node = first; 458 459 while ( node != null ) 460 { 461 keys.add( node.key ); 462 node = node.next; 463 } 464 465 return keys; 466 } 467 468 469 /* (non-Javadoc) 470 * @see org.apache.directory.server.core.avltree.AvlTree#printTree() 471 */ 472 public void printTree() 473 { 474 if ( isEmpty() ) 475 { 476 System.out.println( "Tree is empty" ); 477 return; 478 } 479 480 getRoot().setDepth( 0 ); 481 482 System.out.println( getRoot() ); 483 484 visit( getRoot().getRight(), getRoot() ); 485 486 visit( getRoot().getLeft(), getRoot() ); 487 } 488 489 490 /* (non-Javadoc) 491 * @see org.apache.directory.server.core.avltree.AvlTree#getFirst() 492 */ 493 public LinkedAvlNode<K> getFirst() 494 { 495 return first; 496 } 497 498 499 /* (non-Javadoc) 500 * @see org.apache.directory.server.core.avltree.AvlTree#getLast() 501 */ 502 public LinkedAvlNode<K> getLast() 503 { 504 return last; 505 } 506 507 508 /** 509 * Rotate the node left side once. 510 * 511 * @param node the LinkedAvlNode to be rotated 512 * @param parentNode parent LinkedAvlNode of node 513 */ 514 private void rotateSingleLeft( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode ) 515 { 516 LinkedAvlNode<K> temp; 517 //------rotate single-left-------- 518 519 temp = node.right; 520 node.right = temp.left; 521 temp.left = node; 522 523 if ( node == root ) 524 { 525 root = temp; 526 } 527 else if ( parentNode != null ) 528 { 529 if ( parentNode.left == node ) 530 { 531 parentNode.left = temp; 532 } 533 else if ( parentNode.right == node ) 534 { 535 parentNode.right = temp; 536 } 537 } 538 } 539 540 541 /** 542 * Rotate the node right side once. 543 * 544 * @param node the LinkedAvlNode to be rotated 545 * @param parentNode parent LinkedAvlNode of node 546 */ 547 private void rotateSingleRight( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode ) 548 { 549 LinkedAvlNode<K> temp; 550 //------rotate single-right-------- 551 552 temp = node.left; 553 node.left = temp.right; 554 temp.right = node; 555 556 if ( node == root ) 557 { 558 root = temp; 559 } 560 else if ( parentNode != null ) 561 { 562 if ( parentNode.left == node ) 563 { 564 parentNode.left = temp; 565 } 566 else if ( parentNode.right == node ) 567 { 568 parentNode.right = temp; 569 } 570 } 571 /* 572 when the 'parentNode' param is null then the node under rotation is a child of ROOT. 573 Most likely this condition executes when the root node is deleted and balancing is required. 574 */ 575 else if ( root != null && root.left == node ) 576 { 577 root.left = temp; 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 661 { 662 return find( key, startNode.left, path ); 663 } 664 } 665 666 667 /* (non-Javadoc) 668 * @see org.apache.directory.server.core.avltree.AvlTree#findGreater(K) 669 */ 670 public LinkedAvlNode<K> findGreater( K key ) 671 { 672 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root ); 673 674 if ( result == null ) 675 { 676 return null; 677 } 678 else if ( comparator.compare( key, result.key ) < 0 ) 679 { 680 return result; 681 } 682 683 return result.next; 684 } 685 686 687 /* (non-Javadoc) 688 * @see org.apache.directory.server.core.avltree.AvlTree#findGreaterOrEqual(K) 689 */ 690 public LinkedAvlNode<K> findGreaterOrEqual( K key ) 691 { 692 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root ); 693 694 if ( result == null ) 695 { 696 return null; 697 } 698 else if ( comparator.compare( key, result.key ) <= 0 ) 699 { 700 return result; 701 } 702 703 return result.next; 704 } 705 706 707 /* (non-Javadoc) 708 * @see org.apache.directory.server.core.avltree.AvlTree#findLess(K) 709 */ 710 public LinkedAvlNode<K> findLess( K key ) 711 { 712 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root ); 713 714 if ( result == null ) 715 { 716 return null; 717 } 718 else if ( comparator.compare( key, result.key ) > 0 ) 719 { 720 return result; 721 } 722 723 return result.previous; 724 } 725 726 727 /* (non-Javadoc) 728 * @see org.apache.directory.server.core.avltree.AvlTree#findLessOrEqual(K) 729 */ 730 public LinkedAvlNode<K> findLessOrEqual( K key ) 731 { 732 LinkedAvlNode<K> result = fetchNonNullNode( key, root, root ); 733 734 if ( result == null ) 735 { 736 return null; 737 } 738 else if ( comparator.compare( key, result.key ) >= 0 ) 739 { 740 return result; 741 } 742 743 return result.previous; 744 } 745 746 747 /* 748 * This method returns the last visited non-null node in case if the node with the given key 749 * is not present. This method should not be used as general purpose lookup method. 750 * This is written to assist the findGreater, findLess methods. 751 */ 752 private LinkedAvlNode<K> fetchNonNullNode( K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent ) 753 { 754 755 if ( startNode == null ) 756 { 757 return parent; 758 } 759 760 int c = comparator.compare( key, startNode.key ); 761 762 parent = startNode; 763 764 if ( c > 0 ) 765 { 766 return fetchNonNullNode( key, startNode.right, parent ); 767 } 768 else if ( c < 0 ) 769 { 770 return fetchNonNullNode( key, startNode.left, parent ); 771 } 772 773 return startNode; 774 } 775 776 777 /* (non-Javadoc) 778 * @see org.apache.directory.server.core.avltree.AvlTree#find(K) 779 */ 780 public LinkedAvlNode<K> find( K key ) 781 { 782 return find( key, root ); 783 } 784 785 786 private LinkedAvlNode<K> find( K key, LinkedAvlNode<K> startNode ) 787 { 788 int c; 789 790 if ( startNode == null ) 791 { 792 return null; 793 } 794 795 c = comparator.compare( key, startNode.key ); 796 797 if ( c > 0 ) 798 { 799 startNode.isLeft = false; 800 return find( key, startNode.right ); 801 } 802 else if ( c < 0 ) 803 { 804 startNode.isLeft = true; 805 return find( key, startNode.left ); 806 } 807 808 return startNode; 809 } 810 811 812 /** 813 * Find the LinkedAvlNode having the max key value in the tree starting from the startNode. 814 * 815 * @param startNode starting node of a subtree/tree 816 * @return the list of traversed LinkedAvlNodes. 817 */ 818 private List<LinkedAvlNode<K>> findMax( LinkedAvlNode<K> startNode ) 819 { 820 LinkedAvlNode<K> x = startNode; 821 LinkedAvlNode<K> y = null; 822 List<LinkedAvlNode<K>> path; 823 824 if ( x == null ) 825 { 826 return null; 827 } 828 829 while ( x.right != null ) 830 { 831 x.isLeft = false; 832 y = x; 833 x = x.right; 834 } 835 836 path = new ArrayList<>( 2 ); 837 path.add( x ); 838 839 if ( y != null ) 840 { 841 path.add( y ); 842 } 843 844 return path; 845 } 846 847 848 /** 849 * Find the LinkedAvlNode having the min key value in the tree starting from the startNode. 850 * 851 * @param startNode starting node of a subtree/tree 852 * @return the list of traversed LinkedAvlNodes. 853 */ 854 private List<LinkedAvlNode<K>> findMin( LinkedAvlNode<K> startNode ) 855 { 856 LinkedAvlNode<K> x = startNode; 857 LinkedAvlNode<K> y = null; 858 List<LinkedAvlNode<K>> path; 859 860 if ( x == null ) 861 { 862 return null; 863 } 864 865 while ( x.left != null ) 866 { 867 x.isLeft = true; 868 y = x; 869 x = x.left; 870 } 871 872 path = new ArrayList<>( 2 ); 873 path.add( x ); 874 875 if ( y != null ) 876 { 877 path.add( y ); 878 } 879 880 return path; 881 } 882 883 884 /** 885 * Get balance-factor of the given LinkedAvlNode. 886 * 887 * @param node a LinkedAvlNode 888 * @return balance-factor of the node 889 */ 890 private int getBalance( LinkedAvlNode<K> node ) 891 { 892 if ( node == null ) 893 { 894 return 0; 895 } 896 897 return node.getBalance(); 898 } 899 900 901 private void visit( LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode ) 902 { 903 if ( node == null ) 904 { 905 return; 906 } 907 908 if ( !node.isLeaf() ) 909 { 910 node.setDepth( parentNode.getDepth() + 1 ); 911 } 912 913 for ( int i = 0; i < parentNode.getDepth(); i++ ) 914 { 915 System.out.print( "| " ); 916 } 917 918 String type = ""; 919 if ( node == parentNode.left ) 920 { 921 type = "L"; 922 } 923 else if ( node == parentNode.right ) 924 { 925 type = "R"; 926 } 927 928 System.out.println( "|--" + node + type ); 929 930 if ( node.getRight() != null ) 931 { 932 visit( node.getRight(), node ); 933 } 934 935 if ( node.getLeft() != null ) 936 { 937 visit( node.getLeft(), node ); 938 } 939 } 940}