Binary search tree base AVL implementation. More...
#include <avl_base.hpp>
Classes | |
class | avl_const_iterator |
AVL iterator. More... | |
class | avl_iterator |
AVL iterator. More... | |
class | avl_node |
Node of a binary search tree (AVL). More... | |
Public Types | |
typedef K | value_type |
typedef K | key_type |
typedef K | referent_type |
typedef Comp | key_less |
typedef const K & | const_reference |
typedef avl_iterator | iterator |
typedef avl_const_iterator | const_iterator |
Public Member Functions | |
avl_base () | |
AVL constructor. | |
avl_base (const avl_base< K, Comp > &that) | |
AVL copy constructor. | |
~avl_base () | |
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. | |
iterator | begin () |
Get an iterator on the nodes of the tree. | |
const_iterator | begin () const |
Get an iterator on the nodes of the tree. | |
iterator | end () |
Get an iterator after the end of the tree. | |
const_iterator | end () const |
Get an iterator after the end of the tree. | |
iterator | find (const K &key) |
Get an iterator on the nodes of the tree from a specified key. | |
const_iterator | find (const K &key) const |
Get an iterator on the nodes of the tree from a specified key. | |
iterator | find_nearest_greater (const K &key) |
Get an iterator on the nodes of the tree on the key imediatly after 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. | |
iterator | find_nearest_lower (const K &key) |
Get an iterator on the nodes of the tree on the key imediatly before 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. | |
iterator | lower_bound () |
Get an iterator on the lowest value of the tree. | |
const_iterator | lower_bound () const |
Get an iterator on the lowest value of the tree. | |
iterator | upper_bound () |
Get an iterator on the gratest value of the tree. | |
const_iterator | upper_bound () const |
Get an iterator on the gratest value of the tree. | |
avl_base< K, Comp > & | operator= (const avl_base< K, Comp > &that) |
Assignment operator. | |
bool | operator== (const avl_base< K, Comp > &that) const |
Equality. | |
bool | operator!= (const avl_base< K, Comp > &that) const |
Disequality. | |
bool | operator< (const avl_base< K, Comp > &that) const |
Less than operator. | |
bool | operator> (const avl_base< K, Comp > &that) const |
Greater than operator. | |
bool | operator<= (const avl_base< K, Comp > &that) const |
Less or equal operator. | |
bool | operator>= (const avl_base< K, Comp > &that) const |
Greater or equal operator. | |
void | swap (avl_base< K, Comp > &that) |
Swap the values with an other tree. | |
Static Public Attributes | |
static key_less | s_key_less |
Function object used to compare keys. | |
Private Types | |
typedef avl_node * | avl_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. | |
iterator | make_iterator (avl_node_ptr node) const |
Create an iterator from a pointer to a node. | |
const_iterator | make_const_iterator (const_avl_node_ptr node) const |
Create an iterator from a pointer to a node. | |
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_ptr * | find_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. |
Binary search tree base AVL implementation.
Each key appears only once. Nodes are sorted as left_child < node < right_child.
Definition at line 56 of file avl_base.hpp.
typedef avl_node* claw::avl_base< K, Comp >::avl_node_ptr [private] |
Definition at line 122 of file avl_base.hpp.
typedef avl_node const* claw::avl_base< K, Comp >::const_avl_node_ptr [private] |
Definition at line 123 of file avl_base.hpp.
typedef avl_const_iterator claw::avl_base< K, Comp >::const_iterator |
Definition at line 205 of file avl_base.hpp.
typedef const K& claw::avl_base< K, Comp >::const_reference |
Definition at line 203 of file avl_base.hpp.
typedef avl_iterator claw::avl_base< K, Comp >::iterator |
Definition at line 204 of file avl_base.hpp.
typedef Comp claw::avl_base< K, Comp >::key_less |
Definition at line 202 of file avl_base.hpp.
typedef K claw::avl_base< K, Comp >::key_type |
Definition at line 200 of file avl_base.hpp.
typedef K claw::avl_base< K, Comp >::referent_type |
Definition at line 201 of file avl_base.hpp.
typedef K claw::avl_base< K, Comp >::value_type |
Definition at line 199 of file avl_base.hpp.
claw::avl_base< K, Comp >::avl_base | ( | ) | [inline] |
claw::avl_base< K, Comp >::avl_base | ( | const avl_base< K, Comp > & | that | ) | [inline, explicit] |
AVL copy constructor.
that | AVL instance to copy from. |
Definition at line 915 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.
claw::avl_base< K, Comp >::~avl_base | ( | ) | [inline] |
AVL destructor.
Definition at line 930 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::del_tree(), and claw::avl_base< K, Comp >::m_tree.
void claw::avl_base< K, Comp >::adjust_balance | ( | avl_node_ptr & | node | ) | [inline, private] |
Adjust balance of a node so it will be in range [-1;1].
node | Node to adjust. |
Definition at line 1663 of file avl_base.tpp.
References claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), and claw::avl_base< K, Comp >::avl_node::balance.
Referenced by claw::avl_base< K, Comp >::insert_node().
01664 { 01665 assert(node != NULL); 01666 01667 if ( node->balance == 2) 01668 adjust_balance_left(node); 01669 else if ( node->balance == -2) 01670 adjust_balance_right(node); 01671 } // adjust_balance()
void claw::avl_base< 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].
node | Node to adjust. |
Definition at line 1682 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::left, claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right().
Referenced by claw::avl_base< K, Comp >::adjust_balance(), and claw::avl_base< K, Comp >::new_balance().
01683 { 01684 assert(node != NULL); 01685 assert(node->balance == 2); 01686 01687 if (node->left->balance > -1) 01688 rotate_right( node ); 01689 else if ( node->left->balance == -1) 01690 rotate_left_right(node); 01691 } // adjust_balance_left()
void claw::avl_base< 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].
node | Node to adjust. |
Definition at line 1702 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::right, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right_left().
Referenced by claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::new_balance(), and claw::avl_base< K, Comp >::recursive_delete_node().
01703 { 01704 assert(node != NULL); 01705 assert(node->balance == -2); 01706 01707 if (node->right->balance < 1) 01708 rotate_left( node ); 01709 else if ( node->right->balance == 1) 01710 rotate_right_left(node); 01711 } // adjust_balance_right()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::begin | ( | ) | const [inline] |
Get an iterator on the nodes of the tree.
Definition at line 1053 of file avl_base.tpp.
References claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::m_tree.
01054 { 01055 if (m_tree == NULL) 01056 return const_iterator(NULL, true); 01057 else 01058 return lower_bound(); 01059 } // avl_base::begin()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::begin | ( | ) | [inline] |
Get an iterator on the nodes of the tree.
Definition at line 1039 of file avl_base.tpp.
References claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::m_tree.
Referenced by claw::avl< K, Comp >::begin(), claw::avl_base< K, Comp >::operator<(), and claw::avl_base< K, Comp >::operator==().
01040 { 01041 if (m_tree == NULL) 01042 return iterator(NULL, true); 01043 else 01044 return lower_bound(); 01045 } // avl_base::begin()
bool claw::avl_base< K, Comp >::check_balance | ( | const avl_node_ptr | node | ) | const [inline, private] |
This method will check balance in our trees.
node | Root of the tree to check. |
Definition at line 1358 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::depth(), claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::validity_check().
01359 { 01360 int pl=0, pr=0; 01361 01362 if (node == NULL) 01363 return true; 01364 else 01365 { 01366 if (node->left) pl = node->left->depth(); 01367 if (node->right) pr = node->right->depth(); 01368 01369 return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance) 01370 && check_balance(node->left) && check_balance(node->right); 01371 } 01372 } // check_balance()
bool claw::avl_base< 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.
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. |
Definition at line 1332 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::validity_check().
01333 { 01334 if (node == NULL) 01335 return true; 01336 else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) ) 01337 return (node->left == NULL) 01338 && check_in_bounds( node->right, node->key, max ); 01339 else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) ) 01340 return (node->right == NULL) 01341 && check_in_bounds( node->left, min, node->key ); 01342 else 01343 return s_key_less(node->key, max) && s_key_less(min, node->key) 01344 && check_in_bounds( node->left, min, node->key ) 01345 && check_in_bounds( node->right, node->key, max ); 01346 } // check_less_than()
void claw::avl_base< K, Comp >::clear | ( | ) | [inline] |
Clear a tree.
Definition at line 1000 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::del_tree(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.
Referenced by claw::avl< K, Comp >::clear().
bool claw::avl_base< 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.
node | Node to check. |
Definition at line 1382 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::validity_check().
01383 { 01384 bool valid = true; 01385 01386 if (node != NULL) 01387 { 01388 if (node->father != NULL) 01389 { 01390 valid = (node->father->left == node) ^ (node->father->right == node); 01391 valid = valid && correct_descendant( node->left ) 01392 && correct_descendant( node->right ); 01393 } 01394 else 01395 valid = false; 01396 } 01397 01398 return valid; 01399 } // correct_descendant()
bool claw::avl_base< K, Comp >::empty | ( | ) | const [inline] |
Tell if a tree is empty or not.
Definition at line 1029 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_size.
Referenced by claw::avl< K, Comp >::empty().
01030 { 01031 return m_size == 0; 01032 } // avl_base::empty()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::end | ( | ) | const [inline] |
Get an iterator after the end of the tree.
Definition at line 1080 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::avl_node::upper_bound().
01081 { 01082 if (m_tree == NULL) 01083 return const_iterator(NULL, true); 01084 else 01085 return const_iterator(m_tree->upper_bound(), true); 01086 } // avl_base::end()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::end | ( | ) | [inline] |
Get an iterator after the end of the tree.
Definition at line 1066 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::avl_node::upper_bound().
Referenced by claw::avl< K, Comp >::end(), claw::avl_base< K, Comp >::make_const_iterator(), claw::avl_base< K, Comp >::make_iterator(), claw::avl_base< K, Comp >::operator<(), and claw::avl_base< K, Comp >::operator==().
01067 { 01068 if (m_tree == NULL) 01069 return iterator(NULL, true); 01070 else 01071 return iterator(m_tree->upper_bound(), true); 01072 } // avl_base::end()
void claw::avl_base< K, Comp >::erase | ( | const K & | key | ) | [inline] |
Delete a value in a tree.
key | Node key. |
Definition at line 984 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::recursive_delete(), and claw::avl_base< K, Comp >::validity_check().
Referenced by claw::avl< K, Comp >::erase().
00985 { 00986 assert( validity_check() ); 00987 00988 if (m_tree != NULL) 00989 recursive_delete( m_tree, key ); 00990 00991 assert( validity_check() ); 00992 } // avl_base::erase()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find | ( | const K & | key | ) | const [inline] |
Get an iterator on the nodes of the tree from a specified key.
key | Key to find. |
Definition at line 1107 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().
01108 { 01109 return make_const_iterator( m_tree->find(key) ); 01110 } // avl_base::find()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find | ( | const K & | key | ) | [inline] |
Get an iterator on the nodes of the tree from a specified key.
key | Key to find. |
Definition at line 1095 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().
Referenced by claw::avl< K, Comp >::find().
01096 { 01097 return make_iterator( m_tree->find(key) ); 01098 } // avl_base::find()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< 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.
key | Key to find. |
Definition at line 1133 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().
01134 { 01135 return make_const_iterator( m_tree->find_nearest_greater(key) ); 01136 } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_greater | ( | const K & | key | ) | [inline] |
Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
key | Key to find. |
Definition at line 1120 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().
Referenced by claw::avl< K, Comp >::find_nearest_greater().
01121 { 01122 return make_iterator( m_tree->find_nearest_greater(key) ); 01123 } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< 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.
key | Key to find. |
Definition at line 1159 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().
01160 { 01161 return make_const_iterator( m_tree->find_nearest_lower(key) ); 01162 } // avl_base::find_nearest_lower()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_lower | ( | const K & | key | ) | [inline] |
Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
key | Key to find. |
Definition at line 1146 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().
Referenced by claw::avl< K, Comp >::find_nearest_lower().
01147 { 01148 return make_iterator( m_tree->find_nearest_lower(key) ); 01149 } // avl_base::find_nearest_lower()
claw::avl_base< K, Comp >::avl_node_ptr * claw::avl_base< 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.
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. |
Definition at line 1781 of file avl_base.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::insert_node().
01782 { 01783 avl_node_ptr* node; // node for search 01784 bool exists; // if this key already exists 01785 01786 last_imbalanced = m_tree; 01787 node = & m_tree; 01788 node_father = NULL; 01789 exists = false; 01790 01791 while ( ((*node) != NULL) && !exists ) 01792 { 01793 if ( (*node)->balance != 0 ) 01794 last_imbalanced = *node; 01795 01796 01797 // find next node 01798 if ( s_key_less(key, (*node)->key) ) 01799 { 01800 node_father = *node; 01801 node = & (*node)->left; 01802 } 01803 else if ( s_key_less((*node)->key, key) ) 01804 { 01805 node_father = *node; 01806 node = & (*node)->right; 01807 } 01808 else 01809 exists = true; 01810 } 01811 01812 return node; 01813 } // find_node_reference()
void claw::avl_base< K, Comp >::insert | ( | Iterator | first, | |
Iterator | last | |||
) | [inline] |
Add a range of items in the tree.
Definition at line 971 of file avl_base.tpp.
References claw::avl_base< K, Comp >::insert().
00972 { 00973 for ( ; first!=last; ++first ) 00974 insert( *first ); 00975 } // avl_base::insert()
void claw::avl_base< K, Comp >::insert | ( | const K & | key | ) | [inline] |
Add a value in a tree.
key | Node key. |
Definition at line 946 of file avl_base.tpp.
References claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::validity_check().
Referenced by claw::avl< K, Comp >::avl(), claw::avl_base< K, Comp >::insert(), and claw::avl< K, Comp >::insert().
00947 { 00948 assert( validity_check() ); 00949 00950 if ( m_tree == NULL ) 00951 { 00952 m_tree = new avl_node(key); 00953 m_size = 1; 00954 } 00955 else 00956 insert_node(key); 00957 00958 assert( validity_check() ); 00959 } // avl_base::insert()
void claw::avl_base< K, Comp >::insert_node | ( | const K & | key | ) | [inline, private] |
Add a node to the tree.
key | Key for the new value. |
Definition at line 1727 of file avl_base.tpp.
References claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::find_node_reference(), claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::m_tree, claw::binary_node< U >::right, claw::avl_base< K, Comp >::s_key_less, and claw::avl_base< K, Comp >::update_balance().
Referenced by claw::avl_base< K, Comp >::insert().
01728 { 01729 avl_node_ptr* new_node; 01730 avl_node_ptr node_father; 01731 avl_node_ptr last_imbalanced; 01732 avl_node_ptr last_imbalanced_father; 01733 01734 assert(m_tree != NULL); 01735 01736 new_node = find_node_reference(key, last_imbalanced, node_father ); 01737 01738 if (*new_node == NULL) // this key isn't in use. Let's create a new node 01739 { 01740 *new_node = new avl_node(key); 01741 (*new_node)->father = node_father; 01742 01743 ++m_size; 01744 last_imbalanced_father = last_imbalanced->father; 01745 01746 // Update balance of the last imbalanced node 01747 update_balance( last_imbalanced, key ); 01748 // then adjust it to be in range [-1, 1] 01749 adjust_balance( last_imbalanced ); 01750 01751 // pointer update after rotation 01752 if ( last_imbalanced_father == NULL ) 01753 { 01754 m_tree = last_imbalanced; 01755 m_tree->father = NULL; 01756 } 01757 else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key)) 01758 // left child 01759 last_imbalanced_father->left = last_imbalanced; 01760 else 01761 last_imbalanced_father->right = last_imbalanced; 01762 } 01763 } // insert_node()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::lower_bound | ( | ) | const [inline] |
Get an iterator on the lowest value of the tree.
Definition at line 1180 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::lower_bound(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().
01181 { 01182 return make_const_iterator( m_tree->lower_bound() ); 01183 } // avl_base::lower_bound()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::lower_bound | ( | ) | [inline] |
Get an iterator on the lowest value of the tree.
Definition at line 1169 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::lower_bound(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().
Referenced by claw::avl_base< K, Comp >::begin(), and claw::avl< K, Comp >::lower_bound().
01170 { 01171 return make_iterator( m_tree->lower_bound() ); 01172 } // avl_base::lower_bound()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::make_const_iterator | ( | const_avl_node_ptr | node | ) | const [inline, private] |
Create an iterator from a pointer to a node.
node | The node on which we want the iterator. |
Definition at line 1461 of file avl_base.tpp.
References claw::avl_base< K, Comp >::end().
Referenced by claw::avl_base< K, Comp >::find(), claw::avl_base< K, Comp >::find_nearest_greater(), claw::avl_base< K, Comp >::find_nearest_lower(), claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::upper_bound().
01462 { 01463 if (node != NULL) 01464 return const_iterator(node, false); 01465 else 01466 return end(); 01467 } // avl_base::make_const_iterator()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::make_iterator | ( | avl_node_ptr | node | ) | const [inline, private] |
Create an iterator from a pointer to a node.
node | The node on which we want the iterator. |
Definition at line 1446 of file avl_base.tpp.
References claw::avl_base< K, Comp >::end().
Referenced by claw::avl_base< K, Comp >::find(), claw::avl_base< K, Comp >::find_nearest_greater(), claw::avl_base< K, Comp >::find_nearest_lower(), claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::upper_bound().
bool claw::avl_base< K, Comp >::new_balance | ( | avl_node_ptr & | node, | |
int | imbalance | |||
) | [inline, private] |
Adjust balance of a node.
node | Node to balance. | |
imbalance | Imbalance to add to the node's balance. |
Definition at line 1872 of file avl_base.tpp.
References claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), and claw::avl_base< K, Comp >::avl_node::balance.
Referenced by claw::avl_base< K, Comp >::recursive_delete().
01873 { 01874 assert( (imbalance==1) || (imbalance==-1) ); 01875 assert( node != NULL ); 01876 01877 node->balance += imbalance; 01878 01879 switch(node->balance) 01880 { 01881 // balance == 0 so as it was != 0 before deletion 01882 // balance of the tree had changed 01883 case 0: return true; 01884 // balance == 2 so it must be 1 before deletion and node 01885 // was deleted in the right subtree 01886 // if after ajusting the balance is equal to 1, it means that 01887 // our subtree got back his old balance (so it's unchanged). 01888 // if it's equal to -1, it means that subtree now lean to the 01889 // otherside. But in those cases, depth didn't changed. 01890 case 2: adjust_balance_left(node); return node->balance == 0; 01891 // same thing but symetric 01892 case -2: adjust_balance_right(node); return node->balance == 0; 01893 default : return false; 01894 } 01895 } // new_balance()
bool claw::avl_base< K, Comp >::operator!= | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
bool claw::avl_base< K, Comp >::operator< | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
Less than operator.
that | AVL top compare to. |
Definition at line 1265 of file avl_base.tpp.
References claw::avl_base< K, Comp >::begin(), claw::avl_base< K, Comp >::end(), and claw::avl_base< K, Comp >::s_key_less.
01266 { 01267 return std::lexicographical_compare 01268 ( begin(), end(), that.begin(), that.end(), s_key_less ); 01269 } // avl_base::operator<()
bool claw::avl_base< K, Comp >::operator<= | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
Less or equal operator.
that | AVL top compare to. |
Definition at line 1288 of file avl_base.tpp.
claw::avl_base< K, Comp > & claw::avl_base< K, Comp >::operator= | ( | const avl_base< K, Comp > & | that | ) | [inline] |
Assignment operator.
that | AVL instance to copy from. |
Definition at line 1213 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::del_tree(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.
01214 { 01215 if (this != &that) 01216 { 01217 if (m_tree) 01218 { 01219 m_tree->del_tree(); 01220 delete m_tree; 01221 } 01222 01223 m_size = 0; 01224 01225 if (that.m_tree) 01226 m_tree = that.m_tree->duplicate( m_size ); 01227 else 01228 m_tree = NULL; 01229 } 01230 01231 return *this; 01232 } // avl_base::operator=()
bool claw::avl_base< K, Comp >::operator== | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
Equality.
that | AVL top compare to. |
Definition at line 1240 of file avl_base.tpp.
References claw::avl_base< K, Comp >::begin(), claw::avl_base< K, Comp >::end(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::s_key_less.
01241 { 01242 if (m_size != that.m_size) 01243 return false; 01244 else 01245 return std::equal( begin(), end(), that.begin(), s_key_less ); 01246 } // avl_base::operator==()
bool claw::avl_base< K, Comp >::operator> | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
Greater than operator.
that | AVL top compare to. |
Definition at line 1277 of file avl_base.tpp.
bool claw::avl_base< K, Comp >::operator>= | ( | const avl_base< K, Comp > & | that | ) | const [inline] |
Greater or equal operator.
that | AVL top compare to. |
Definition at line 1299 of file avl_base.tpp.
bool claw::avl_base< K, Comp >::recursive_delete | ( | avl_node_ptr & | node, | |
const K & | key | |||
) | [inline, private] |
Delete a node. Search is done recursively.
node | Tree to which the node is removed. | |
key | Key of the node to remove. |
Definition at line 1832 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::new_balance(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.
Referenced by claw::avl_base< K, Comp >::erase().
01833 { 01834 bool result = false; 01835 01836 if ( node != NULL ) 01837 { 01838 // try to find the key in the left subtree 01839 if ( s_key_less(key, node->key) ) 01840 { 01841 if ( recursive_delete( node->left, key ) ) 01842 result = new_balance( node, -1 ); 01843 } 01844 // try to find the key in the right subtree 01845 else if ( s_key_less(node->key, key) ) 01846 { 01847 if ( recursive_delete( node->right, key ) ) 01848 result = new_balance( node, 1 ); 01849 } 01850 else // we got it ! 01851 { 01852 --m_size; 01853 result = recursive_delete_node( node ); 01854 } 01855 } 01856 01857 return result; 01858 } // recursive_delete()
int claw::avl_base< 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.
root | Root of the tree in which find new values. | |
node | Node Wich gets values founded |
Definition at line 1976 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::recursive_delete_node().
01977 { 01978 assert(node!=NULL); 01979 assert(root!=NULL); 01980 01981 if ( root->right == NULL ) // We have the maximum 01982 { 01983 // node have only a left subtree if any. 01984 // This subtree has one node, at most. 01985 avl_node_ptr left_subtree; 01986 01987 node->key = root->key; 01988 left_subtree = root->left; 01989 01990 if (left_subtree) 01991 left_subtree->father = root->father; 01992 01993 root->clear(); 01994 delete root; 01995 01996 // rise the left subtree 01997 root = left_subtree; 01998 01999 // depth have changed 02000 return true; 02001 } 02002 else // try to find the max in the right subtree 02003 if ( recursive_delete_max( root->right, node ) ) 02004 { 02005 // depth of the subtree changed (ie. decreased) 02006 // so root's tree lean to the left 02007 ++(root->balance); 02008 02009 if (root->balance == 2) // tree is leaning too much 02010 { 02011 // old balance was 1 02012 adjust_balance_left( root ); 02013 return root->balance == 0; // Say if balance is changed 02014 } 02015 else 02016 // if balance is 0, it means that old root leant to the left 02017 // and so his depth changed. 02018 // The other value for balance is 1, in this case 02019 // depth didn't change. See recursive_delete_node code comments. 02020 return root->balance == 0; 02021 } 02022 else // depth of the subtree didn't change 02023 return false; 02024 } // recursive_delete_max()
bool claw::avl_base< K, Comp >::recursive_delete_node | ( | avl_node_ptr & | node | ) | [inline, private] |
Remove the root of an AVL (exchange with the descendant immediatly lower).
node | Node to remove. |
Definition at line 1907 of file avl_base.tpp.
References claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, claw::avl_base< K, Comp >::recursive_delete_max(), and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::recursive_delete().
01908 { 01909 assert( node != NULL ); 01910 01911 if ( node->left == NULL) // this node doesn't have a lower descendant 01912 { 01913 // Get right subtree of current node 01914 avl_node_ptr right_subtree = node->right; 01915 01916 if (right_subtree) 01917 right_subtree->father = node->father; 01918 01919 // Free memory pointed by the current node 01920 node->clear(); 01921 delete node; 01922 01923 // then rise the old right subtree 01924 node = right_subtree; 01925 01926 return true; 01927 } 01928 else // this node has a lower descendant, let's get it 01929 if ( recursive_delete_max( node->left, node ) ) 01930 { 01931 // left subtree depth has decreased 01932 // so reajust balance (rem. balance is not changed by delete_max) 01933 --(node->balance); 01934 01935 if ( node->balance == -2 ) 01936 { 01937 // old balance was -1 01938 adjust_balance_right(node); 01939 return node->balance == 0; // tell if depth has changed 01940 } 01941 else if ( node->balance == 0 ) 01942 // node had at least one subtree and old balance - 1 == 0 01943 // so old balance = 1 01944 return true; 01945 else // node's balance is -1 01946 // As node's balance is (old balance - 1), node's balance must be -1 01947 // (otherwise old balance is 2, that's impossible) 01948 // So old balance is 0. 01949 // Moreover old node have at least a left subtree. It means that 01950 // old node had 2 subtrees and their depths were equals. 01951 // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1 01952 // We deleted a node in left subtree and so right subtree is 01953 // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 01954 // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node) 01955 // => Node depth is unchanged. 01956 return false; 01957 } 01958 else // depth is unchanged 01959 return false; 01960 } // recursive_delete_node()
void claw::avl_base< K, Comp >::rotate_left | ( | avl_node_ptr & | node | ) | [inline, private] |
Node left rotation.
node | Node to rotate. |
Definition at line 1545 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right_left().
01546 { 01547 avl_node_ptr p; 01548 char old_node_balance; 01549 char old_subtree_balance; 01550 01551 assert( node != NULL ); 01552 assert( node->right != NULL ); 01553 assert( (-2 <= node->balance) && (node->balance <= -1) ) ; 01554 assert( (-2 <= node->right->balance) && (node->right->balance <= 1) ); 01555 assert( (node->right->balance != -2) || (node->balance == -2) ); 01556 01557 old_node_balance = node->balance; 01558 old_subtree_balance = node->right->balance; 01559 01560 // rotate nodes 01561 p = node->right; 01562 p->father = node->father; 01563 01564 node->right = p->left; 01565 01566 if (p->left) 01567 p->left->father = node; 01568 01569 p->left = node; 01570 node->father = p; 01571 01572 node = p; 01573 01574 // adjust balance 01575 switch(old_subtree_balance) 01576 { 01577 case -2 : 01578 // old_node_balance is -2 too. 01579 node->balance = 0; 01580 node->left->balance = 1; 01581 break; 01582 case -1 : 01583 node->balance = old_node_balance + 2; 01584 node->left->balance = old_node_balance + 2; 01585 break; 01586 case 0 : 01587 node->balance = 1; 01588 node->left->balance = old_node_balance + 1; 01589 break; 01590 case 1 : 01591 node->balance = 2; 01592 node->left->balance = old_node_balance + 1; 01593 break; 01594 } 01595 } // rotate_left()
void claw::avl_base< K, Comp >::rotate_left_right | ( | avl_node_ptr & | node | ) | [inline, private] |
Node left-right rotation.
node | Node to rotate. |
Definition at line 1603 of file avl_base.tpp.
References claw::binary_node< U >::left, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right().
Referenced by claw::avl_base< K, Comp >::adjust_balance_left().
01604 { 01605 assert( node != NULL ); 01606 01607 rotate_left( node->left ); 01608 rotate_right( node ); 01609 } // rotate_left_right()
void claw::avl_base< K, Comp >::rotate_right | ( | avl_node_ptr & | node | ) | [inline, private] |
Node right rotation.
node | Node to rotate. |
Definition at line 1484 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right_left().
01485 { 01486 avl_node_ptr p; 01487 char old_node_balance; 01488 char old_subtree_balance; 01489 01490 assert( node != NULL ); 01491 assert( node->left != NULL ); 01492 assert( (1 <= node->balance) && (node->balance <= 2) ) ; 01493 assert( (-1 <= node->left->balance) && (node->left->balance <= 2) ); 01494 assert( (node->left->balance != 2) || (node->balance == 2) ); 01495 01496 old_node_balance = node->balance; 01497 old_subtree_balance = node->left->balance; 01498 01499 // rotate nodes 01500 p = node->left; 01501 p->father = node->father; 01502 01503 node->left = p->right; 01504 01505 if (p->right) 01506 p->right->father = node; 01507 01508 p->right = node; 01509 node->father = p; 01510 01511 node = p; 01512 01513 // adjust balance 01514 switch(old_subtree_balance) 01515 { 01516 case -1 : 01517 node->balance = -2; 01518 node->right->balance = old_node_balance - 1; 01519 break; 01520 case 0 : 01521 node->balance = -1; 01522 node->right->balance = old_node_balance - 1; 01523 break; 01524 case 1 : 01525 node->balance = old_node_balance - 2; 01526 node->right->balance = old_node_balance - 2; 01527 break; 01528 case 2 : 01529 // old_node_balance is 2 too. 01530 node->balance = 0; 01531 node->right->balance = - 1; 01532 break; 01533 } 01534 } // rotate_right()
void claw::avl_base< K, Comp >::rotate_right_left | ( | avl_node_ptr & | node | ) | [inline, private] |
Node right-left rotation.
node | Node to rotate. |
Definition at line 1617 of file avl_base.tpp.
References claw::binary_node< U >::right, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right().
Referenced by claw::avl_base< K, Comp >::adjust_balance_right().
01618 { 01619 assert( node != NULL ); 01620 01621 rotate_right( node->right ); 01622 rotate_left( node ); 01623 } // rotate_right_left()
unsigned int claw::avl_base< K, Comp >::size | ( | ) | const [inline] |
Get the size of a tree.
Definition at line 1018 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_size.
Referenced by claw::avl< K, Comp >::size().
01019 { 01020 return m_size; 01021 } // avl_base::size()
void claw::avl_base< K, Comp >::swap | ( | avl_base< K, Comp > & | that | ) | [inline] |
Swap the values with an other tree.
that | The other tree. |
Definition at line 1310 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.
void claw::avl_base< 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.
node | Root of the subtree to update. | |
key | Key of the just-added node. |
Definition at line 1635 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.
Referenced by claw::avl_base< K, Comp >::insert_node().
01636 { 01637 assert(node != NULL); 01638 bool done = false; 01639 01640 while (!done) 01641 if ( s_key_less(key, node->key) ) 01642 { 01643 ++node->balance; 01644 node = node->left; 01645 } 01646 else if ( s_key_less(node->key, key) ) 01647 { 01648 --node->balance; 01649 node = node->right; 01650 } 01651 else 01652 done = true; 01653 } // update_balance()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::upper_bound | ( | ) | const [inline] |
Get an iterator on the gratest value of the tree.
Definition at line 1201 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::make_const_iterator(), and claw::avl_base< K, Comp >::avl_node::upper_bound().
01202 { 01203 return make_const_iterator( m_tree->upper_bound() ); 01204 } // avl_base::upper_bound()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::upper_bound | ( | ) | [inline] |
Get an iterator on the gratest value of the tree.
Definition at line 1190 of file avl_base.tpp.
References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::make_iterator(), and claw::avl_base< K, Comp >::avl_node::upper_bound().
Referenced by claw::avl< K, Comp >::upper_bound().
01191 { 01192 return make_iterator( m_tree->upper_bound() ); 01193 } // avl_base::upper_bound()
bool claw::avl_base< K, Comp >::validity_check | ( | ) | const [inline, private] |
This method will check orderliness in our trees : balance and order.
Definition at line 1409 of file avl_base.tpp.
References claw::avl_base< K, Comp >::check_balance(), claw::avl_base< K, Comp >::check_in_bounds(), claw::avl_base< K, Comp >::correct_descendant(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_tree, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::erase(), and claw::avl_base< K, Comp >::insert().
01410 { 01411 bool valid = true; 01412 01413 if (m_tree != NULL) 01414 { 01415 avl_node *node_min, *node_max; 01416 01417 // get lower and higher bounds, hope they are correct 01418 for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left); 01419 for (node_max = m_tree; node_max->right!=NULL; 01420 node_max = node_max->right); 01421 01422 valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key); 01423 valid = valid 01424 && check_in_bounds(m_tree->right, m_tree->key, node_max->key); 01425 01426 valid = valid && (m_tree->father == NULL) 01427 && correct_descendant( m_tree->left ) 01428 && correct_descendant( m_tree->right ); 01429 01430 } 01431 01432 return valid && check_balance(m_tree); 01433 } // validity_check()
unsigned int claw::avl_base< K, Comp >::m_size [private] |
Nodes count.
Definition at line 310 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::avl_base(), claw::avl_base< K, Comp >::clear(), claw::avl_base< K, Comp >::empty(), claw::avl_base< K, Comp >::insert(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::operator=(), claw::avl_base< K, Comp >::operator==(), claw::avl_base< K, Comp >::recursive_delete(), claw::avl_base< K, Comp >::size(), and claw::avl_base< K, Comp >::swap().
avl_node_ptr claw::avl_base< K, Comp >::m_tree [private] |
Nodes.
Definition at line 313 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::avl_base(), claw::avl_base< K, Comp >::begin(), claw::avl_base< K, Comp >::clear(), claw::avl_base< K, Comp >::end(), claw::avl_base< K, Comp >::erase(), claw::avl_base< K, Comp >::find(), claw::avl_base< K, Comp >::find_nearest_greater(), claw::avl_base< K, Comp >::find_nearest_lower(), claw::avl_base< K, Comp >::insert(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::lower_bound(), claw::avl_base< K, Comp >::operator=(), claw::avl_base< K, Comp >::swap(), claw::avl_base< K, Comp >::upper_bound(), claw::avl_base< K, Comp >::validity_check(), and claw::avl_base< K, Comp >::~avl_base().
claw::avl_base< K, Comp >::key_less claw::avl_base< K, Comp >::s_key_less [inline, static] |
Function object used to compare keys.
Definition at line 306 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::operator<(), claw::avl_base< K, Comp >::operator==(), claw::avl_base< K, Comp >::recursive_delete(), and claw::avl_base< K, Comp >::update_balance().