00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #include <cassert>
00031
00032
00033
00034
00039 template<class K, class Comp>
00040 claw::avl<K, Comp>::avl_node::avl_node( const K& k )
00041 : super(), key(k), balance(0), father(NULL)
00042 {
00043 assert(!super::left);
00044 assert(!super::right);
00045 }
00046
00047
00051 template<class K, class Comp>
00052 claw::avl<K, Comp>::avl_node::~avl_node()
00053 {
00054
00055 }
00056
00057
00063 template<class K, class Comp>
00064 typename claw::avl<K, Comp>::avl_node*
00065 claw::avl<K, Comp>::avl_node::duplicate( unsigned int& count ) const
00066 {
00067 avl_node* node_copy = new avl_node(key);
00068 ++count;
00069 node_copy->balance = balance;
00070 node_copy->father = NULL;
00071
00072 if (super::left)
00073 {
00074 node_copy->left = super::left->duplicate(count);
00075 node_copy->left->father = node_copy;
00076 }
00077 else
00078 node_copy->left = NULL;
00079
00080 if (super::right)
00081 {
00082 node_copy->right = super::right->duplicate(count);
00083 node_copy->right->father = node_copy;
00084 }
00085 else
00086 node_copy->right = NULL;
00087
00088 return node_copy;
00089 }
00090
00091
00096 template<class K, class Comp>
00097 void claw::avl<K, Comp>::avl_node::del_tree()
00098 {
00099 if (super::left)
00100 {
00101 delete super::left;
00102 super::left = NULL;
00103 }
00104 if (super::right)
00105 {
00106 delete super::right;
00107 super::right = NULL;
00108 }
00109 assert( !super::left );
00110 assert( !super::right );
00111 }
00112
00113
00119 template<class K, class Comp>
00120 unsigned int claw::avl<K, Comp>::avl_node::depth() const
00121 {
00122 unsigned int pl=0, pr=0;
00123
00124 if (super::left) pl = super::left->depth();
00125 if (super::right) pr = super::right->depth();
00126
00127 if (pl > pr)
00128 return 1 + pl;
00129 else
00130 return 1 + pr;
00131 }
00132
00133
00134
00135
00136
00137
00138
00139
00140
00146 template<class K, class Comp>
00147 claw::avl<K, Comp>::avl_node::avl_node( const avl_node& that )
00148 : super(that), key(that.key), balance(that.balance), father(NULL)
00149 {
00150 assert(0);
00151 }
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00165 template<class K, class Comp>
00166 claw::avl<K,Comp>::avl_iterator::avl_iterator()
00167 : m_current(NULL), m_is_final(true)
00168 {
00169
00170 }
00171
00172
00176 template<class K, class Comp>
00177 claw::avl<K,Comp>::avl_iterator::avl_iterator( const_avl_node_ptr node,
00178 bool final )
00179 : m_current(node), m_is_final(final)
00180 {
00181
00182 }
00183
00184
00198 template<class K, class Comp>
00199 typename claw::avl<K,Comp>::avl_iterator&
00200 claw::avl<K,Comp>::avl_iterator::operator++()
00201 {
00202 assert(!m_is_final);
00203 assert(m_current);
00204
00205
00206 if (m_current->right != NULL)
00207 {
00208 m_current = m_current->right;
00209
00210 while (m_current->left != NULL)
00211 m_current = m_current->left;
00212 }
00213 else
00214 {
00215 bool done = false;
00216 const_avl_node_ptr previous_node = m_current;
00217
00218
00219 while (m_current->father && !done)
00220 {
00221 if (m_current->father->left == m_current)
00222 done = true;
00223
00224 m_current = m_current->father;
00225 }
00226
00227
00228 if (!done)
00229 {
00230 m_current = previous_node;
00231 m_is_final = true;
00232 }
00233 }
00234
00235 return *this;
00236 }
00237
00238
00242 template<class K, class Comp>
00243 typename claw::avl<K,Comp>::avl_iterator
00244 claw::avl<K,Comp>::avl_iterator::operator++(int)
00245 {
00246 avl_iterator it = *this;
00247 ++(*this);
00248 return it;
00249 }
00250
00251
00265 template<class K, class Comp>
00266 typename claw::avl<K,Comp>::avl_iterator&
00267 claw::avl<K,Comp>::avl_iterator::operator--()
00268 {
00269 assert(m_current);
00270
00271 if (m_is_final)
00272 m_is_final = !m_is_final;
00273 else
00274 if (m_current->left != NULL)
00275 {
00276 m_current = m_current->left;
00277
00278 while (m_current->right != NULL)
00279 m_current = m_current->right;
00280 }
00281 else
00282 {
00283 bool done = false;
00284
00285
00286 while (m_current->father && !done)
00287 {
00288 if (m_current->father->right == m_current)
00289 done = true;
00290
00291 m_current = m_current->father;
00292 }
00293
00294
00295 assert(done);
00296 }
00297
00298 return *this;
00299 }
00300
00301
00305 template<class K, class Comp>
00306 typename claw::avl<K,Comp>::avl_iterator
00307 claw::avl<K,Comp>::avl_iterator::operator--(int)
00308 {
00309 avl_iterator it = *this;
00310 --(*this);
00311 return it;
00312 }
00313
00314
00318 template<class K, class Comp>
00319 typename claw::avl<K,Comp>::avl_iterator::reference
00320 claw::avl<K,Comp>::avl_iterator::operator*() const
00321 {
00322 return m_current->key;
00323 }
00324
00325
00329 template<class K, class Comp>
00330 typename claw::avl<K,Comp>::avl_iterator::pointer
00331 claw::avl<K,Comp>::avl_iterator::operator->() const
00332 {
00333 return &m_current->key;
00334 }
00335
00336
00341 template<class K, class Comp>
00342 bool claw::avl<K,Comp>::avl_iterator::operator==(const avl_iterator& it) const
00343 {
00344 return (m_current == it.m_current) && (m_is_final == it.m_is_final);
00345 }
00346
00347
00352 template<class K, class Comp>
00353 bool claw::avl<K,Comp>::avl_iterator::operator!=(const avl_iterator& it) const
00354 {
00355 return !( *this == it );
00356 }
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366 template<class K, class Comp>
00367 typename claw::avl<K,Comp>::key_less claw::avl<K,Comp>::s_key_less;
00368
00369
00374 template<class K, class Comp>
00375 claw::avl<K,Comp>::avl()
00376 : m_size(0), m_tree(NULL)
00377 {
00378
00379 }
00380
00381
00386 template<class K, class Comp>
00387 claw::avl<K,Comp>::avl( const avl<K, Comp>& that )
00388 {
00389 m_size = 0;
00390
00391 if (that.m_tree)
00392 m_tree = that.m_tree->duplicate( m_size );
00393 else
00394 m_tree = NULL;
00395 }
00396
00397
00401 template<class K, class Comp>
00402 claw::avl<K,Comp>::~avl()
00403 {
00404 if (m_tree)
00405 {
00406 m_tree->del_tree();
00407 delete m_tree;
00408 }
00409 }
00410
00411
00417 template<class K, class Comp>
00418 void claw::avl<K,Comp>::insert( const K& key )
00419 {
00420 assert( validity_check() );
00421
00422 if ( m_tree == NULL )
00423 {
00424 m_tree = new avl_node(key);
00425 m_size = 1;
00426 }
00427 else
00428 insert_node(key);
00429
00430 assert( validity_check() );
00431 }
00432
00433
00441 template<class K, class Comp>
00442 template<typename Iterator>
00443 void claw::avl<K,Comp>::insert( Iterator first, Iterator last )
00444 {
00445 for ( ; first!=last; ++first )
00446 insert( *first );
00447 }
00448
00449
00455 template<class K, class Comp>
00456 void claw::avl<K,Comp>::erase( const K& key )
00457 {
00458 assert( validity_check() );
00459
00460 if (m_tree != NULL)
00461 recursive_delete( m_tree, key );
00462
00463 assert( validity_check() );
00464 }
00465
00466
00471 template<class K, class Comp>
00472 void claw::avl<K,Comp>::clear()
00473 {
00474 if (m_tree != NULL)
00475 {
00476 m_tree->del_tree();
00477 delete m_tree;
00478
00479 m_tree = NULL;
00480 m_size = 0;
00481 }
00482 }
00483
00484
00489 template<class K, class Comp>
00490 inline unsigned int claw::avl<K,Comp>::size() const
00491 {
00492 return m_size;
00493 }
00494
00495
00500 template<class K, class Comp>
00501 inline bool claw::avl<K,Comp>::empty() const
00502 {
00503 return m_size == 0;
00504 }
00505
00506
00510 template<class K, class Comp>
00511 typename claw::avl<K,Comp>::const_iterator
00512 claw::avl<K,Comp>::begin() const
00513 {
00514 return lower_bound();
00515 }
00516
00517
00521 template<class K, class Comp>
00522 typename claw::avl<K,Comp>::const_iterator claw::avl<K,Comp>::end() const
00523 {
00524 const_avl_node_ptr node = m_tree;
00525
00526 if (node)
00527 while (node->right)
00528 node = node->right;
00529
00530 return const_iterator(node, true);
00531 }
00532
00533
00538 template<class K, class Comp>
00539 typename claw::avl<K,Comp>::const_iterator
00540 claw::avl<K,Comp>::find( const K& key ) const
00541 {
00542 bool ok;
00543 const_avl_node_ptr node = m_tree;
00544
00545 ok = false;
00546
00547 while (node && !ok)
00548 if ( s_key_less(key, node->key) )
00549 node = node->left;
00550 else if ( s_key_less(node->key, key) )
00551 node = node->right;
00552 else
00553 ok = true;
00554
00555 if (node != NULL)
00556 return const_iterator(node, false);
00557 else
00558 return end();
00559 }
00560
00561
00567 template<class K, class Comp>
00568 typename claw::avl<K,Comp>::const_iterator
00569 claw::avl<K,Comp>::find_nearest_greater( const K& key ) const
00570 {
00571 bool ok;
00572 const_avl_node_ptr node = m_tree;
00573 const_avl_node_ptr prev_node = NULL;
00574
00575 ok = false;
00576
00577 while (node && !ok)
00578 if ( s_key_less(key, node->key) )
00579 {
00580 prev_node = node;
00581 node = node->left;
00582 }
00583 else if ( s_key_less(node->key, key) )
00584 {
00585 prev_node = node;
00586 node = node->right;
00587 }
00588 else
00589 ok = true;
00590
00591 if (ok)
00592 return ++const_iterator(node, false);
00593 else if (prev_node)
00594 {
00595 if ( s_key_less(key, prev_node->key) )
00596 return ++const_iterator(prev_node, false);
00597 else
00598 return const_iterator(prev_node, false);
00599 }
00600 else if (node != NULL)
00601 return const_iterator(node, false);
00602 else
00603 return end();
00604 }
00605
00606
00612 template<class K, class Comp>
00613 typename claw::avl<K,Comp>::const_iterator
00614 claw::avl<K,Comp>::find_nearest_lower( const K& key ) const
00615 {
00616 bool ok;
00617 const_avl_node_ptr node = m_tree;
00618 const_avl_node_ptr prev_node = NULL;
00619
00620 ok = false;
00621
00622 while (node && !ok)
00623 if ( s_key_less(key, node->key) )
00624 {
00625 prev_node = node;
00626 node = node->left;
00627 }
00628 else if ( s_key_less(node->key, key) )
00629 {
00630 prev_node = node;
00631 node = node->right;
00632 }
00633 else
00634 ok = true;
00635
00636 if (ok)
00637 return --const_iterator(node, false);
00638 else if (prev_node)
00639 {
00640 if ( s_key_less(key, prev_node->key) )
00641 return const_iterator(prev_node, false);
00642 else
00643 return --const_iterator(prev_node, false);
00644 }
00645 else if (node != NULL)
00646 return const_iterator(node, false);
00647 else
00648 return end();
00649 }
00650
00651
00655 template<class K, class Comp>
00656 typename claw::avl<K,Comp>::const_iterator
00657 claw::avl<K,Comp>::lower_bound() const
00658 {
00659 const_avl_node_ptr node = m_tree;
00660
00661 if (node)
00662 while (node->left)
00663 node = node->left;
00664
00665 if (node != NULL)
00666 return const_iterator(node, false);
00667 else
00668 return end();
00669 }
00670
00671
00675 template<class K, class Comp>
00676 typename claw::avl<K,Comp>::const_iterator
00677 claw::avl<K,Comp>::upper_bound() const
00678 {
00679 const_avl_node_ptr node = m_tree;
00680
00681 if (node)
00682 while (node->right)
00683 node = node->right;
00684
00685 if (node != NULL)
00686 return const_iterator(node, false);
00687 else
00688 return end();
00689 }
00690
00691
00696 template<class K, class Comp>
00697 claw::avl<K,Comp>& claw::avl<K,Comp>::operator=( const avl<K, Comp>& that )
00698 {
00699 if (m_tree)
00700 {
00701 m_tree->del_tree();
00702 delete m_tree;
00703 }
00704
00705 m_size = 0;
00706
00707 if (that.m_tree)
00708 m_tree = that.m_tree->duplicate( m_size );
00709 else
00710 m_tree = NULL;
00711
00712 return *this;
00713 }
00714
00715
00716
00717
00718
00719
00720
00729 template<class K, class Comp>
00730 bool claw::avl<K,Comp>::check_in_bounds( const avl_node_ptr node, const K& min,
00731 const K& max ) const
00732 {
00733 if (node == NULL)
00734 return true;
00735 else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
00736 return (node->left == NULL)
00737 && check_in_bounds( node->right, node->key, max );
00738 else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
00739 return (node->right == NULL)
00740 && check_in_bounds( node->left, min, node->key );
00741 else
00742 return s_key_less(node->key, max) && s_key_less(min, node->key)
00743 && check_in_bounds( node->left, min, node->key )
00744 && check_in_bounds( node->right, node->key, max );
00745 }
00746
00747
00756 template<class K, class Comp>
00757 bool claw::avl<K,Comp>::check_balance( const avl_node_ptr node ) const
00758 {
00759 int pl=0, pr=0;
00760
00761 if (node == NULL)
00762 return true;
00763 else
00764 {
00765 if (node->left) pl = node->left->depth();
00766 if (node->right) pr = node->right->depth();
00767
00768 return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
00769 && check_balance(node->left) && check_balance(node->right);
00770 }
00771 }
00772
00773
00780 template<class K, class Comp>
00781 bool claw::avl<K,Comp>::correct_descendant( const avl_node_ptr node ) const
00782 {
00783 bool valid = true;
00784
00785 if (node != NULL)
00786 {
00787 if (node->father != NULL)
00788 {
00789 valid = (node->father->left == node) ^ (node->father->right == node);
00790 valid = valid && correct_descendant( node->left )
00791 && correct_descendant( node->right );
00792 }
00793 else
00794 valid = false;
00795 }
00796
00797 return valid;
00798 }
00799
00800
00807 template<class K, class Comp>
00808 bool claw::avl<K,Comp>::validity_check() const
00809 {
00810 bool valid = true;
00811
00812 if (m_tree != NULL)
00813 {
00814 avl_node *node_min, *node_max;
00815
00816
00817 for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
00818 for (node_max = m_tree; node_max->right!=NULL;
00819 node_max = node_max->right);
00820
00821 valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
00822 valid = valid
00823 && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
00824
00825 valid = valid && (m_tree->father == NULL)
00826 && correct_descendant( m_tree->left )
00827 && correct_descendant( m_tree->right );
00828
00829 }
00830
00831 return valid && check_balance(m_tree);
00832 }
00833
00834
00835
00836
00837
00838
00839
00840
00841
00849 template<class K, class Comp>
00850 void claw::avl<K,Comp>::rotate_right( avl_node_ptr& node )
00851 {
00852 avl_node_ptr p;
00853 char old_node_balance;
00854 char old_subtree_balance;
00855
00856 assert( node != NULL );
00857 assert( node->left != NULL );
00858 assert( (1 <= node->balance) && (node->balance <= 2) ) ;
00859 assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
00860 assert( (node->left->balance != 2) || (node->balance == 2) );
00861
00862 old_node_balance = node->balance;
00863 old_subtree_balance = node->left->balance;
00864
00865
00866 p = node->left;
00867 p->father = node->father;
00868
00869 node->left = p->right;
00870
00871 if (p->right)
00872 p->right->father = node;
00873
00874 p->right = node;
00875 node->father = p;
00876
00877 node = p;
00878
00879
00880 switch(old_subtree_balance)
00881 {
00882 case -1 :
00883 node->balance = -2;
00884 node->right->balance = old_node_balance - 1;
00885 break;
00886 case 0 :
00887 node->balance = -1;
00888 node->right->balance = old_node_balance - 1;
00889 break;
00890 case 1 :
00891 node->balance = old_node_balance - 2;
00892 node->right->balance = old_node_balance - 2;
00893 break;
00894 case 2 :
00895
00896 node->balance = 0;
00897 node->right->balance = - 1;
00898 break;
00899 }
00900 }
00901
00902
00910 template<class K, class Comp>
00911 void claw::avl<K,Comp>::rotate_left( avl_node_ptr& node )
00912 {
00913 avl_node_ptr p;
00914 char old_node_balance;
00915 char old_subtree_balance;
00916
00917 assert( node != NULL );
00918 assert( node->right != NULL );
00919 assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
00920 assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
00921 assert( (node->right->balance != -2) || (node->balance == -2) );
00922
00923 old_node_balance = node->balance;
00924 old_subtree_balance = node->right->balance;
00925
00926
00927 p = node->right;
00928 p->father = node->father;
00929
00930 node->right = p->left;
00931
00932 if (p->left)
00933 p->left->father = node;
00934
00935 p->left = node;
00936 node->father = p;
00937
00938 node = p;
00939
00940
00941 switch(old_subtree_balance)
00942 {
00943 case -2 :
00944
00945 node->balance = 0;
00946 node->left->balance = 1;
00947 break;
00948 case -1 :
00949 node->balance = old_node_balance + 2;
00950 node->left->balance = old_node_balance + 2;
00951 break;
00952 case 0 :
00953 node->balance = 1;
00954 node->left->balance = old_node_balance + 1;
00955 break;
00956 case 1 :
00957 node->balance = 2;
00958 node->left->balance = old_node_balance + 1;
00959 break;
00960 }
00961 }
00962
00963
00968 template<class K, class Comp>
00969 void claw::avl<K,Comp>::rotate_left_right( avl_node_ptr& node )
00970 {
00971 assert( node != NULL );
00972
00973 rotate_left( node->left );
00974 rotate_right( node );
00975 }
00976
00977
00982 template<class K, class Comp>
00983 void claw::avl<K,Comp>::rotate_right_left( avl_node_ptr& node )
00984 {
00985 assert( node != NULL );
00986
00987 rotate_right( node->right );
00988 rotate_left( node );
00989 }
00990
00991
01000 template<class K, class Comp>
01001 void claw::avl<K,Comp>::update_balance( avl_node_ptr node, const K& key )
01002 {
01003 assert(node != NULL);
01004 bool done = false;
01005
01006 while (!done)
01007 if ( s_key_less(key, node->key) )
01008 {
01009 ++node->balance;
01010 node = node->left;
01011 }
01012 else if ( s_key_less(node->key, key) )
01013 {
01014 --node->balance;
01015 node = node->right;
01016 }
01017 else
01018 done = true;
01019 }
01020
01021
01028 template<class K, class Comp>
01029 void claw::avl<K,Comp>::adjust_balance( avl_node_ptr& node )
01030 {
01031 assert(node != NULL);
01032
01033 if ( node->balance == 2)
01034 adjust_balance_left(node);
01035 else if ( node->balance == -2)
01036 adjust_balance_right(node);
01037 }
01038
01039
01047 template<class K, class Comp>
01048 void claw::avl<K,Comp>::adjust_balance_left( avl_node_ptr& node )
01049 {
01050 assert(node != NULL);
01051 assert(node->balance == 2);
01052
01053 if (node->left->balance > -1)
01054 rotate_right( node );
01055 else if ( node->left->balance == -1)
01056 rotate_left_right(node);
01057 }
01058
01059
01067 template<class K, class Comp>
01068 void claw::avl<K,Comp>::adjust_balance_right( avl_node_ptr& node )
01069 {
01070 assert(node != NULL);
01071 assert(node->balance == -2);
01072
01073 if (node->right->balance < 1)
01074 rotate_left( node );
01075 else if ( node->right->balance == 1)
01076 rotate_right_left(node);
01077 }
01078
01079
01080
01081
01082
01083
01084
01085
01092 template<class K, class Comp>
01093 void claw::avl<K,Comp>::insert_node( const K& key )
01094 {
01095 avl_node_ptr* new_node;
01096 avl_node_ptr node_father;
01097 avl_node_ptr last_imbalanced;
01098 avl_node_ptr last_imbalanced_father;
01099
01100 assert(m_tree != NULL);
01101
01102 new_node = find_node_reference(key, last_imbalanced, node_father );
01103
01104 if (*new_node == NULL)
01105 {
01106 *new_node = new avl_node(key);
01107 (*new_node)->father = node_father;
01108
01109 ++m_size;
01110 last_imbalanced_father = last_imbalanced->father;
01111
01112
01113 update_balance( last_imbalanced, key );
01114
01115 adjust_balance( last_imbalanced );
01116
01117
01118 if ( last_imbalanced_father == NULL )
01119 {
01120 m_tree = last_imbalanced;
01121 m_tree->father = NULL;
01122 }
01123 else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key))
01124
01125 last_imbalanced_father->left = last_imbalanced;
01126 else
01127 last_imbalanced_father->right = last_imbalanced;
01128 }
01129 }
01130
01143 template<class K, class Comp>
01144 typename claw::avl<K,Comp>::avl_node_ptr*
01145 claw::avl<K,Comp>::find_node_reference( const K& key,
01146 avl_node_ptr& last_imbalanced,
01147 avl_node_ptr& node_father)
01148 {
01149 avl_node_ptr* node;
01150 bool exists;
01151
01152 last_imbalanced = m_tree;
01153 node = & m_tree;
01154 node_father = NULL;
01155 exists = false;
01156
01157 while ( ((*node) != NULL) && !exists )
01158 {
01159 if ( (*node)->balance != 0 )
01160 last_imbalanced = *node;
01161
01162
01163
01164 if ( s_key_less(key, (*node)->key) )
01165 {
01166 node_father = *node;
01167 node = & (*node)->left;
01168 }
01169 else if ( s_key_less((*node)->key, key) )
01170 {
01171 node_father = *node;
01172 node = & (*node)->right;
01173 }
01174 else
01175 exists = true;
01176 }
01177
01178 return node;
01179 }
01180
01181
01182
01183
01184
01185
01186
01187
01196 template<class K, class Comp>
01197 bool claw::avl<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
01198 {
01199 bool result = false;
01200
01201 if ( node != NULL )
01202 {
01203
01204 if ( s_key_less(key, node->key) )
01205 {
01206 if ( recursive_delete( node->left, key ) )
01207 result = new_balance( node, -1 );
01208 }
01209
01210 else if ( s_key_less(node->key, key) )
01211 {
01212 if ( recursive_delete( node->right, key ) )
01213 result = new_balance( node, 1 );
01214 }
01215 else
01216 {
01217 --m_size;
01218 result = recursive_delete_node( node );
01219 }
01220 }
01221
01222 return result;
01223 }
01224
01225
01226
01236 template<class K, class Comp>
01237 bool claw::avl<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
01238 {
01239 assert( (imbalance==1) || (imbalance==-1) );
01240 assert( node != NULL );
01241
01242 node->balance += imbalance;
01243
01244 switch(node->balance)
01245 {
01246
01247
01248 case 0: return true;
01249
01250
01251
01252
01253
01254
01255 case 2: adjust_balance_left(node); return node->balance == 0;
01256
01257 case -2: adjust_balance_right(node); return node->balance == 0;
01258 default : return false;
01259 }
01260 }
01261
01262
01271 template<class K, class Comp>
01272 bool claw::avl<K,Comp>::recursive_delete_node( avl_node_ptr& node )
01273 {
01274 assert( node != NULL );
01275
01276 if ( node->left == NULL)
01277 {
01278
01279 avl_node_ptr right_subtree = node->right;
01280
01281 if (right_subtree)
01282 right_subtree->father = node->father;
01283
01284
01285 node->clear();
01286 delete node;
01287
01288
01289 node = right_subtree;
01290
01291 return true;
01292 }
01293 else
01294 if ( recursive_delete_max( node->left, node ) )
01295 {
01296
01297
01298 --(node->balance);
01299
01300 if ( node->balance == -2 )
01301 {
01302
01303 adjust_balance_right(node);
01304 return node->balance == 0;
01305 }
01306 else if ( node->balance == 0 )
01307
01308
01309 return true;
01310 else
01311
01312
01313
01314
01315
01316
01317
01318
01319
01320
01321 return false;
01322 }
01323 else
01324 return false;
01325 }
01326
01327
01339 template<class K, class Comp>
01340 int claw::avl<K,Comp>::recursive_delete_max( avl_node_ptr& root,
01341 avl_node_ptr node )
01342 {
01343 assert(node!=NULL);
01344 assert(root!=NULL);
01345
01346 if ( root->right == NULL )
01347 {
01348
01349
01350 avl_node_ptr left_subtree;
01351
01352 node->key = root->key;
01353 left_subtree = root->left;
01354
01355 if (left_subtree)
01356 left_subtree->father = root->father;
01357
01358 root->clear();
01359 delete root;
01360
01361
01362 root = left_subtree;
01363
01364
01365 return true;
01366 }
01367 else
01368 if ( recursive_delete_max( root->right, node ) )
01369 {
01370
01371
01372 ++(root->balance);
01373
01374 if (root->balance == 2)
01375 {
01376
01377 adjust_balance_left( root );
01378 return root->balance == 0;
01379 }
01380 else
01381
01382
01383
01384
01385 return root->balance == 0;
01386 }
01387 else
01388 return false;
01389 }