claw::avl< K, Comp > Class Template Reference

#include <avl.hpp>

Inheritance diagram for claw::avl< K, Comp >:

claw::math::ordered_set< K, Comp >

List of all members.


Detailed Description

template<class K, class Comp = std::less<K>>
class claw::avl< K, Comp >

Binary search tree AVL implementation.

Each key appears only once. Nodes are sorted as left_child < node < right_child.

Invariant:
this->empty() <==> (this->size() == 0)

this is an AVL.

Remarks:
Type requirements :
  • K is LessThanComparable ;
  • Comp is a binary predicate such that Comp(K a, K b) == true if a < b.

Code is taken from a C implementation, so perhaps it doesn't really look nice for C++. Nevertheless it works perfectly and it's fast conversion : that good things.

Author:
Julien Jorge

Definition at line 59 of file avl.hpp.


Public Types

typedef const K value_type
typedef K key_type
typedef K referent_type
typedef Comp key_less
typedef const K & const_reference
typedef avl_iterator const_iterator

Public Member Functions

 avl ()
 AVL constructor.
 avl (const avl< K, Comp > &that)
 AVL copy constructor.
 ~avl ()
 AVL destructor.
void insert (const K &key)
 Add a value in a tree.
template<typename Iterator>
void insert (Iterator first, Iterator last)
 Add a range of items in the tree.
void erase (const K &key)
 Delete a value in a tree.
void clear ()
 Clear a tree.
unsigned int size () const
 Get the size of a tree.
bool empty () const
 Tell if a tree is empty or not.
const_iterator begin () const
 Get an iterator on the nodes of the tree.
const_iterator end () const
 Get an iterator after the end of the tree.
const_iterator find (const K &key) const
 Get an iterator on the nodes of the tree from a specified key.
const_iterator find_nearest_greater (const K &key) const
 Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
const_iterator find_nearest_lower (const K &key) const
 Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
const_iterator lower_bound () const
 Get an iterator on the lowest value of the tree.
const_iterator upper_bound () const
 Get an iterator on the gratest value of the tree.
avl< K, Comp > & operator= (const avl< K, Comp > &that)
 Assignment operator.

Static Protected Attributes

static key_less s_key_less
 Function object used to compare keys.

Private Types

typedef avl_nodeavl_node_ptr
typedef avl_node const * const_avl_node_ptr

Private Member Functions

bool check_in_bounds (const avl_node_ptr node, const K &min, const K &max) const
 This method will check order in our trees.
bool check_balance (const avl_node_ptr node) const
 This method will check balance in our trees.
bool correct_descendant (const avl_node_ptr node) const
 This method will check if each node is a son of his father.
bool validity_check () const
 This method will check orderliness in our trees : balance and order.
void rotate_right (avl_node_ptr &node)
 Node right rotation.
void rotate_left (avl_node_ptr &node)
 Node left rotation.
void rotate_left_right (avl_node_ptr &node)
 Node left-right rotation.
void rotate_right_left (avl_node_ptr &node)
 Node right-left rotation.
void update_balance (avl_node_ptr node, const K &key)
 Update balance of each node by increasing depth of the substree containing key, from node to the node key.
void adjust_balance (avl_node_ptr &node)
 Adjust balance of a node so it will be in range [-1;1].
void adjust_balance_left (avl_node_ptr &node)
 Adjust balance of a node leaning on the left so it will be in range [-1;1].
void adjust_balance_right (avl_node_ptr &node)
 Adjust balance of a node leaning on the right so it will be in range [-1;1].
void insert_node (const K &key)
 Add a node to the tree.
avl_node_ptrfind_node_reference (const K &key, avl_node_ptr &last_imbalanced, avl_node_ptr &node_father)
 Find the node where to insert a new value at key.
bool recursive_delete (avl_node_ptr &node, const K &key)
 Delete a node. Search is done recursively.
bool new_balance (avl_node_ptr &node, int imbalance)
 Adjust balance of a node.
bool recursive_delete_node (avl_node_ptr &node)
 Remove the root of an AVL (exchange with the descendant immediatly lower).
int recursive_delete_max (avl_node_ptr &root, avl_node_ptr node)
 Replace a node key and data by the one of the node with the maximum key in tree.

Private Attributes

unsigned int m_size
 Nodes count.
avl_node_ptr m_tree
 Nodes.

Classes

class  avl_iterator
 AVL iterator. More...
class  avl_node
 Node of a binary search tree (AVL). More...

Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef avl_node* claw::avl< K, Comp >::avl_node_ptr [private]

Definition at line 99 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef avl_node const* claw::avl< K, Comp >::const_avl_node_ptr [private]

Definition at line 100 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef const K claw::avl< K, Comp >::value_type

template<class K, class Comp = std::less<K>>
typedef K claw::avl< K, Comp >::key_type

Definition at line 140 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef K claw::avl< K, Comp >::referent_type

template<class K, class Comp = std::less<K>>
typedef Comp claw::avl< K, Comp >::key_less

Definition at line 142 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef const K& claw::avl< K, Comp >::const_reference

template<class K, class Comp = std::less<K>>
typedef avl_iterator claw::avl< K, Comp >::const_iterator


Constructor & Destructor Documentation

template<class K, class Comp>
claw::avl< K, Comp >::avl (  )  [inline]

AVL constructor.

Postcondition:
empty()

Definition at line 375 of file avl.tpp.

00376   : m_size(0), m_tree(NULL) 
00377 {
00378 
00379 } // avl::avl() [constructeur]

template<class K, class Comp>
claw::avl< K, Comp >::avl ( const avl< K, Comp > &  that  )  [inline, explicit]

AVL copy constructor.

Parameters:
that AVL instance to copy from.

Definition at line 387 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::duplicate(), claw::avl< K, Comp >::m_size, and claw::avl< K, Comp >::m_tree.

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]

template<class K, class Comp>
claw::avl< K, Comp >::~avl (  )  [inline]

AVL destructor.

Definition at line 402 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::del_tree(), and claw::avl< K, Comp >::m_tree.

00403 {
00404   if (m_tree)
00405     {
00406       m_tree->del_tree();
00407       delete m_tree;
00408     }
00409 } // avl::~avl() [destructeur]


Member Function Documentation

template<class K, class Comp>
void claw::avl< K, Comp >::insert ( const K &  key  )  [inline]

Add a value in a tree.

Parameters:
key Node key.
Postcondition:
exists(key)

Definition at line 418 of file avl.tpp.

References claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::m_size, claw::avl< K, Comp >::m_tree, and claw::avl< K, Comp >::validity_check().

Referenced by claw::arguments::add_argument(), claw::avl< K, Comp >::insert(), claw::math::ordered_set< K, Comp >::join(), claw::arguments_table::parse(), and claw::automaton< State, Edge, StateComp, EdgeComp >::reachables().

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()

template<class K, class Comp>
template<typename Iterator>
void claw::avl< K, Comp >::insert ( Iterator  first,
Iterator  last 
) [inline]

Add a range of items in the tree.

Parameters:
first Iterator on the first item to add.
last Iterator past the last item to add.
Precondition:
Iterator::value_type is K
Postcondition:
exists( *it ) for all it in [first, last)

Definition at line 443 of file avl.tpp.

References claw::avl< K, Comp >::insert().

00444 {
00445   for ( ; first!=last; ++first )
00446     insert( *first );
00447 } // avl::insert()

template<class K, class Comp>
void claw::avl< K, Comp >::erase ( const K &  key  )  [inline]

Delete a value in a tree.

Parameters:
key Node key.
Postcondition:
not exists(key)

Definition at line 456 of file avl.tpp.

References claw::avl< K, Comp >::m_tree, claw::avl< K, Comp >::recursive_delete(), and claw::avl< K, Comp >::validity_check().

Referenced by claw::math::ordered_set< K, Comp >::difference(), and claw::math::ordered_set< K, Comp >::intersection().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::clear (  )  [inline]

Clear a tree.

Postcondition:
empty()

Definition at line 472 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::del_tree(), claw::avl< K, Comp >::m_size, and claw::avl< K, Comp >::m_tree.

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()

template<class K, class Comp>
unsigned int claw::avl< K, Comp >::size (  )  const [inline]

Get the size of a tree.

Returns:
The size of the tree.

Definition at line 490 of file avl.tpp.

References claw::avl< K, Comp >::m_size.

Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), and claw::math::ordered_set< K, Comp >::strictly_contains().

00491 {
00492   return m_size; 
00493 } // avl::size()

template<class K, class Comp>
bool claw::avl< K, Comp >::empty (  )  const [inline]

Tell if a tree is empty or not.

Returns:
true if the tree is empty, false otherwise.

Definition at line 501 of file avl.tpp.

References claw::avl< K, Comp >::m_size.

00502 {
00503   return m_size == 0; 
00504 } // avl::empty()

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::begin (  )  const [inline]

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::end (  )  const [inline]

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree from a specified key.

Parameters:
key Key to find.

Definition at line 540 of file avl.tpp.

References claw::avl< K, Comp >::end(), claw::binary_node< U >::left, claw::avl< K, Comp >::m_tree, and claw::avl< K, Comp >::s_key_less.

Referenced by claw::math::ordered_set< K, Comp >::difference(), claw::arguments::get_bool(), claw::math::ordered_set< K, Comp >::intersection(), and claw::arguments::parse().

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()

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find_nearest_greater ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree on the key imediatly after from a specified key.

Parameters:
key Key to find.

Definition at line 569 of file avl.tpp.

References claw::avl< K, Comp >::end(), claw::binary_node< U >::left, claw::avl< K, Comp >::m_tree, and claw::avl< K, Comp >::s_key_less.

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()

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find_nearest_lower ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree on the key imediatly before from a specified key.

Parameters:
key Key to find.

Definition at line 614 of file avl.tpp.

References claw::avl< K, Comp >::end(), claw::binary_node< U >::left, claw::avl< K, Comp >::m_tree, and claw::avl< K, Comp >::s_key_less.

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()

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::lower_bound (  )  const [inline]

Get an iterator on the lowest value of the tree.

Definition at line 657 of file avl.tpp.

References claw::avl< K, Comp >::end(), claw::binary_node< U >::left, and claw::avl< K, Comp >::m_tree.

Referenced by claw::avl< K, Comp >::begin().

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()

template<class K, class Comp>
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::upper_bound (  )  const [inline]

Get an iterator on the gratest value of the tree.

Definition at line 677 of file avl.tpp.

References claw::avl< K, Comp >::end(), claw::avl< K, Comp >::m_tree, and claw::binary_node< U >::right.

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()

template<class K, class Comp>
claw::avl< K, Comp > & claw::avl< K, Comp >::operator= ( const avl< K, Comp > &  that  )  [inline]

Assignment operator.

Parameters:
that AVL instance to copy from.

Definition at line 697 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::del_tree(), claw::avl< K, Comp >::avl_node::duplicate(), claw::avl< K, Comp >::m_size, and claw::avl< K, Comp >::m_tree.

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=()

template<class K, class Comp>
bool claw::avl< K, Comp >::check_in_bounds ( const avl_node_ptr  node,
const K &  min,
const K &  max 
) const [inline, private]

This method will check order in our trees.

Parameters:
node Root of the tree to check.
min Lower bound of the valid range for tree's nodes.
max Higher bound of the valid range for tree's nodes.
Remarks:
For validity check.
Returns:
true if bounds are ok, false otherwise.

Definition at line 730 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::binary_node< U >::right, and claw::avl< K, Comp >::s_key_less.

Referenced by claw::avl< K, Comp >::validity_check().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::check_balance ( const avl_node_ptr  node  )  const [inline, private]

This method will check balance in our trees.

Parameters:
node Root of the tree to check.
Remarks:
For validity check.
Returns:
true if the absolute difference between left subtree's depth and right subtree's depth is 1 for node and each of its subtrees. false otherwise.

Definition at line 757 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::validity_check().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::correct_descendant ( const avl_node_ptr  node  )  const [inline, private]

This method will check if each node is a son of his father.

Parameters:
node Node to check.
Remarks:
For validity check.
Returns:
true if the AVL is valid, false otherwise.

Definition at line 781 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::validity_check().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::validity_check (  )  const [inline, private]

This method will check orderliness in our trees : balance and order.

Remarks:
For validity check.
Returns:
true if the AVL is valid, false otherwise.

Definition at line 808 of file avl.tpp.

References claw::avl< K, Comp >::check_balance(), claw::avl< K, Comp >::check_in_bounds(), claw::avl< K, Comp >::correct_descendant(), claw::avl< K, Comp >::avl_node::father, claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl< K, Comp >::m_tree, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::erase(), and claw::avl< K, Comp >::insert().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::rotate_right ( avl_node_ptr node  )  [inline, private]

Node right rotation.

Parameters:
node Node to rotate.
Precondition:
(node != NULL) && node->left != NULL

node->balance in [1,2] and node->left->balance in [-1,2]

(node->left->balance == 2) ==> (node->balance == 2)

Definition at line 850 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::avl< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::adjust_balance_left(), claw::avl< K, Comp >::rotate_left_right(), and claw::avl< K, Comp >::rotate_right_left().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::rotate_left ( avl_node_ptr node  )  [inline, private]

Node left rotation.

Parameters:
node Node to rotate.
Precondition:
(node != NULL) && node->right != NULL

node->balance in [-2,-1] and node->right->balance in [-2,1]

(node->right->balance == -2) ==> (node->balance == -2)

Definition at line 911 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::avl< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::adjust_balance_right(), claw::avl< K, Comp >::rotate_left_right(), and claw::avl< K, Comp >::rotate_right_left().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::rotate_left_right ( avl_node_ptr node  )  [inline, private]

Node left-right rotation.

Parameters:
node Node to rotate.

Definition at line 969 of file avl.tpp.

References claw::binary_node< U >::left, claw::avl< K, Comp >::rotate_left(), and claw::avl< K, Comp >::rotate_right().

Referenced by claw::avl< K, Comp >::adjust_balance_left().

00970 {
00971   assert( node != NULL );
00972 
00973   rotate_left( node->left );
00974   rotate_right( node );
00975 } // rotate_left_right()

template<class K, class Comp>
void claw::avl< K, Comp >::rotate_right_left ( avl_node_ptr node  )  [inline, private]

Node right-left rotation.

Parameters:
node Node to rotate.

Definition at line 983 of file avl.tpp.

References claw::binary_node< U >::right, claw::avl< K, Comp >::rotate_left(), and claw::avl< K, Comp >::rotate_right().

Referenced by claw::avl< K, Comp >::adjust_balance_right().

00984 {
00985   assert( node != NULL );
00986 
00987   rotate_right( node->right );
00988   rotate_left( node );
00989 } // rotate_right_left()

template<class K, class Comp>
void claw::avl< K, Comp >::update_balance ( avl_node_ptr  node,
const K &  key 
) [inline, private]

Update balance of each node by increasing depth of the substree containing key, from node to the node key.

Parameters:
node Root of the subtree to update.
key Key of the just-added node.
Precondition:
(node != NULL) && ( key is in the tree starting from root node )
Postcondition:
balance is ok for each node from node to key

Definition at line 1001 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::binary_node< U >::right, and claw::avl< K, Comp >::s_key_less.

Referenced by claw::avl< K, Comp >::insert_node().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::adjust_balance ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1029 of file avl.tpp.

References claw::avl< K, Comp >::adjust_balance_left(), claw::avl< K, Comp >::adjust_balance_right(), and claw::avl< K, Comp >::avl_node::balance.

Referenced by claw::avl< K, Comp >::insert_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()

template<class K, class Comp>
void claw::avl< K, Comp >::adjust_balance_left ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node leaning on the left so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL) && (*node != NULL) && ( (*node)->balance == 2).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1048 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::binary_node< U >::left, claw::avl< K, Comp >::rotate_left_right(), and claw::avl< K, Comp >::rotate_right().

Referenced by claw::avl< K, Comp >::adjust_balance(), claw::avl< K, Comp >::new_balance(), and claw::avl< K, Comp >::recursive_delete_max().

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()

template<class K, class Comp>
void claw::avl< K, Comp >::adjust_balance_right ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node leaning on the right so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL) && (*node != NULL) && ( (*node)->balance == -2).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1068 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::balance, claw::binary_node< U >::right, claw::avl< K, Comp >::rotate_left(), and claw::avl< K, Comp >::rotate_right_left().

Referenced by claw::avl< K, Comp >::adjust_balance(), claw::avl< K, Comp >::new_balance(), and claw::avl< K, Comp >::recursive_delete_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()

template<class K, class Comp>
void claw::avl< K, Comp >::insert_node ( const K &  key  )  [inline, private]

Add a node to the tree.

Parameters:
key Key for the new value.
Postcondition:
exists(key) && (exists(old this, key)==0 => size(this) == size(old this) + 1 )

Definition at line 1093 of file avl.tpp.

References claw::avl< K, Comp >::adjust_balance(), claw::avl< K, Comp >::avl_node::father, claw::avl< K, Comp >::find_node_reference(), claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl< K, Comp >::m_size, claw::avl< K, Comp >::m_tree, claw::binary_node< U >::right, claw::avl< K, Comp >::s_key_less, and claw::avl< K, Comp >::update_balance().

Referenced by claw::avl< K, Comp >::insert().

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()

template<class K, class Comp>
claw::avl< K, Comp >::avl_node_ptr * claw::avl< K, Comp >::find_node_reference ( const K &  key,
avl_node_ptr last_imbalanced,
avl_node_ptr node_father 
) [inline, private]

Find the node where to insert a new value at key.

Parameters:
key Key for the new value.
last_imbalanced (out) Pointer to the last imbalanced node seen.
node_father (out) Pointer to the father of the new node.
Returns:
Pointer to the node corresponding of the key (if exists). Otherwise a pointer to a NULL node where to insert the new one.
Postcondition:
( exists(this, key) => *result == find(this, key) ) && ( !exists(this, key) => *result the good node to allocate ) && ( *last_imbalance and *last_imbalance are correct regarding to previous definitions )

Definition at line 1145 of file avl.tpp.

References claw::binary_node< U >::left, claw::avl< K, Comp >::m_tree, claw::binary_node< U >::right, and claw::avl< K, Comp >::s_key_less.

Referenced by claw::avl< K, Comp >::insert_node().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::recursive_delete ( avl_node_ptr node,
const K &  key 
) [inline, private]

Delete a node. Search is done recursively.

Parameters:
node Tree to which the node is removed.
key Key of the node to remove.
Returns:
true if the balance of the node has changed.
Precondition:
node != NULL
Postcondition:
(exists(this, key) == 0)

Definition at line 1197 of file avl.tpp.

References claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl< K, Comp >::m_size, claw::avl< K, Comp >::new_balance(), claw::avl< K, Comp >::recursive_delete_node(), claw::binary_node< U >::right, and claw::avl< K, Comp >::s_key_less.

Referenced by claw::avl< K, Comp >::erase().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::new_balance ( avl_node_ptr node,
int  imbalance 
) [inline, private]

Adjust balance of a node.

Parameters:
node Node to balance.
imbalance Imbalance to add to the node's balance.
Returns:
true if the balance of the node has changed.
Precondition:
node != NULL

(imbalance==1) || (imbalance==-1)

Postcondition:
node tree is an AVL

Definition at line 1237 of file avl.tpp.

References claw::avl< K, Comp >::adjust_balance_left(), claw::avl< K, Comp >::adjust_balance_right(), and claw::avl< K, Comp >::avl_node::balance.

Referenced by claw::avl< K, Comp >::recursive_delete().

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()

template<class K, class Comp>
bool claw::avl< K, Comp >::recursive_delete_node ( avl_node_ptr node  )  [inline, private]

Remove the root of an AVL (exchange with the descendant immediatly lower).

Parameters:
node Node to remove.
Returns:
true if the balance of the subtree has changed.
Precondition:
node != NULL
Postcondition:
node tree is an AVL

Definition at line 1272 of file avl.tpp.

References claw::avl< K, Comp >::adjust_balance_right(), claw::avl< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl< K, Comp >::avl_node::father, claw::binary_node< U >::left, claw::avl< K, Comp >::recursive_delete_max(), and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::recursive_delete().

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()

template<class K, class Comp>
int claw::avl< K, Comp >::recursive_delete_max ( avl_node_ptr root,
avl_node_ptr  node 
) [inline, private]

Replace a node key and data by the one of the node with the maximum key in tree.

Parameters:
root Root of the tree in which find new values.
node Node Wich gets values founded
Returns:
true if the balance of the tree from root has changed.
Precondition:
node != NULL

root != NULL

root is an AVL

Postcondition:
(root tree is an AVL) && (find(root, max(old root)) == 0)

Definition at line 1340 of file avl.tpp.

References claw::avl< K, Comp >::adjust_balance_left(), claw::avl< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl< K, Comp >::avl_node::father, claw::avl< K, Comp >::avl_node::key, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl< K, Comp >::recursive_delete_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()


Member Data Documentation

template<class K, class Comp = std::less<K>>
claw::avl< K, Comp >::key_less claw::avl< K, Comp >::s_key_less [inline, static, protected]

template<class K, class Comp = std::less<K>>
unsigned int claw::avl< K, Comp >::m_size [private]

template<class K, class Comp = std::less<K>>
avl_node_ptr claw::avl< K, Comp >::m_tree [private]


The documentation for this class was generated from the following files:

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