avl.tpp

Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #include <cassert>
00031 
00032 //******************************* avl::avl_node *******************************
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 } // avl_node::avl_node() [constructeur]
00046 
00047 /*---------------------------------------------------------------------------*/
00051 template<class K, class Comp>
00052 claw::avl<K, Comp>::avl_node::~avl_node() 
00053 {
00054 
00055 } // avl_node::~avl_node() [destructeur]
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 } // avl_node::duplicate()
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 } // avl_node::del_tree
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 } // avl_node::depth()
00132 
00133 
00134 
00135 
00136 /*=================================== private ===============================*/
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 } // avl_node::depth()
00152 
00153 
00154 
00155 
00156 
00157 //******************************* avl::avl_iterator ***************************
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 } // avl_iterator::avl_iterator() [constructeur]
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 } // avl_iterator::avl_iterator() [constructeur with node]
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   // node have a right subtree : go to the min
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       // get parent node
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       // came back up from the max node to the root
00228       if (!done)
00229         {
00230           m_current = previous_node;
00231           m_is_final = true;
00232         }
00233     }
00234                         
00235   return *this;
00236 } // avl_iterator::operator++() [preincrement]
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 } // avl_iterator::operator++ [postincrement]
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  // node have a left subtree : go to the max
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         // get parent node
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         // came back up from the max node to the root
00295         assert(done);
00296       }
00297   
00298   return *this;
00299 } // avl_iterator::operator--() [predecrement]
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 } // avl_iterator::operator-- [postdecrement]
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 } // avl_iterator::operator*() [dereference]
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 } // avl_iterator::operator->()
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 } // avl_iterator::operator==()
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 } // avl_iterator::operator!=()
00357 
00358 
00359 
00360 
00361 
00362 //********************************* avl (main) ********************************
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 } // avl::avl() [constructeur]
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 } // avl::avl() [copy constructor]
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 } // avl::~avl() [destructeur]
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 } // avl::insert()
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 } // avl::insert()
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 } // avl::erase()
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 } // avl::clear()
00483 
00484 /*---------------------------------------------------------------------------*/
00489 template<class K, class Comp>
00490 inline unsigned int claw::avl<K,Comp>::size() const
00491 {
00492   return m_size; 
00493 } // avl::size()
00494 
00495 /*---------------------------------------------------------------------------*/
00500 template<class K, class Comp>
00501 inline bool claw::avl<K,Comp>::empty() const
00502 {
00503   return m_size == 0; 
00504 } // avl::empty()
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 } // avl::begin()
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 } // avl::end()
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 } // avl::find()
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 } // avl::find_nearest_greater()
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 } // avl::find_nearest_lower()
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 } // avl::lower_bound()
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 } // avl::upper_bound()
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 } // avl::operator=()
00714 
00715 /*================================= private =================================*/
00716 
00717 //-----------------------------------------------------------------------------
00718 // We need some methods to check the validity of our trees
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 } // check_less_than()
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 } // check_balance()
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 } // correct_descendant()
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       // get lower and higher bounds, hope they are correct
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 } // validity_check()
00833 
00834 
00835 
00836 
00837 
00838 //-----------------------------------------------------------------------------
00839 // Tree management methods
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   // rotate nodes
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   // adjust balance
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       // old_node_balance is 2 too.
00896       node->balance = 0;
00897       node->right->balance = - 1;
00898       break;
00899     }
00900 } // rotate_right()
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   // rotate nodes
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   // adjust balance
00941   switch(old_subtree_balance)
00942     {
00943     case  -2 :
00944       // old_node_balance is -2 too.
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 } // rotate_left()
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 } // rotate_left_right()
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 } // rotate_right_left()
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 } // update_balance()
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 } // adjust_balance()
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 } // adjust_balance_left()
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 } // adjust_balance_right()
01078 
01079 
01080 /*---------------------------------------------------------------------------*/
01081 //    Methods for insertion
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) // this key isn't in use. Let's create a new node
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       // Update balance of the last imbalanced node
01113       update_balance( last_imbalanced, key );
01114       // then adjust it to be in range [-1, 1]
01115       adjust_balance( last_imbalanced );
01116                   
01117       // pointer update after rotation
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         // left child
01125         last_imbalanced_father->left = last_imbalanced;
01126       else
01127         last_imbalanced_father->right = last_imbalanced;
01128     }
01129 } // insert_node()
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; // node for search
01150   bool exists;        // if this key already 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       // find next node
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 } // find_node_reference()
01180 
01181 
01182 /*---------------------------------------------------------------------------*/
01183 //    Methods for deletion
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       // try to find the key in the left subtree
01204       if ( s_key_less(key, node->key) ) 
01205         {
01206           if ( recursive_delete( node->left, key ) )
01207             result = new_balance( node, -1 );
01208         }
01209       // try to find the key in the right subtree
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 // we got it !
01216         {
01217           --m_size;
01218           result = recursive_delete_node( node );
01219         }
01220     }
01221 
01222   return result;
01223 } // recursive_delete()
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       // balance == 0 so as it was != 0 before deletion
01247       // balance of the tree had changed
01248     case 0: return true;
01249       // balance == 2 so it must be 1 before deletion and node
01250       // was deleted in the right subtree
01251       // if after ajusting the balance is equal to 1, it means that
01252       // our subtree got back his old balance (so it's unchanged).
01253       // if it's equal to -1, it means that subtree now lean to the
01254       // otherside. But in those cases, depth didn't changed.
01255     case 2: adjust_balance_left(node); return node->balance == 0;
01256       // same thing but symetric
01257     case -2: adjust_balance_right(node); return node->balance == 0;
01258     default : return false;
01259     }
01260 } // new_balance()
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) // this node doesn't have a lower descendant
01277     {
01278       // Get right subtree of current node
01279       avl_node_ptr right_subtree = node->right; 
01280 
01281       if (right_subtree)
01282         right_subtree->father = node->father;
01283 
01284       // Free memory pointed by the current node
01285       node->clear();
01286       delete node;
01287 
01288       // then rise the old right subtree
01289       node = right_subtree;
01290 
01291       return true;
01292     }
01293   else // this node has a lower descendant, let's get it
01294     if ( recursive_delete_max( node->left, node ) )
01295       {
01296         // left subtree depth has decreased
01297         // so reajust balance (rem. balance is not changed by delete_max)
01298         --(node->balance);
01299 
01300         if ( node->balance == -2 )
01301           {
01302             // old balance was -1
01303             adjust_balance_right(node);
01304             return node->balance == 0; // tell if depth has changed
01305           }
01306         else if ( node->balance == 0 ) 
01307           // node had at least one subtree and old balance - 1 == 0
01308           // so old balance = 1
01309           return true;
01310         else // node's balance is -1
01311           // As node's balance is (old balance - 1), node's balance must be -1
01312           // (otherwise old balance is 2, that's impossible)
01313           // So old balance is 0.
01314           // Moreover old node have at least a left subtree. It means that 
01315           // old node had 2 subtrees and their depths were equals.
01316           // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1
01317           // We deleted a node in left subtree and so right subtree is
01318           // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 
01319           // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node)
01320           // => Node depth is unchanged.
01321           return false;
01322       }
01323     else // depth is unchanged
01324       return false;
01325 } // recursive_delete_node()
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 ) // We have the maximum
01347     {
01348       // node have only a left subtree if any.
01349       // This subtree has one node, at most.
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       // rise the left subtree
01362       root = left_subtree;
01363 
01364       // depth have changed
01365       return true;
01366     }
01367   else // try to find the max in the right subtree
01368     if ( recursive_delete_max( root->right, node ) )
01369       {
01370         // depth of the subtree changed (ie. decreased)
01371         // so root's tree lean to the left
01372         ++(root->balance);
01373 
01374         if (root->balance == 2) // tree is leaning too much
01375           {
01376             // old balance was 1
01377             adjust_balance_left( root );
01378             return root->balance == 0; // Say if balance is changed
01379           }
01380         else 
01381           // if balance is 0, it means that old root leant to the left
01382           // and so his depth changed.
01383           // The other value for balance is 1, in this case
01384           // depth didn't change. See recursive_delete_node code comments.
01385           return root->balance == 0;
01386       }
01387     else // depth of the subtree didn't change
01388       return false;
01389 } // recursive_delete_max()

Generated on Thu May 22 21:07:35 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.5