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 | ( | ) |
claw::avl_base< K, Comp >::avl_base | ( | const avl_base< K, Comp > & | that | ) | [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 | ( | ) |
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 | ) | [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().
{ assert(node != NULL); if ( node->balance == 2) adjust_balance_left(node); else if ( node->balance == -2) adjust_balance_right(node); } // adjust_balance()
void claw::avl_base< K, Comp >::adjust_balance_left | ( | avl_node_ptr & | node | ) | [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().
{ assert(node != NULL); assert(node->balance == 2); if (node->left->balance > -1) rotate_right( node ); else if ( node->left->balance == -1) rotate_left_right(node); } // adjust_balance_left()
void claw::avl_base< K, Comp >::adjust_balance_right | ( | avl_node_ptr & | node | ) | [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().
{ assert(node != NULL); assert(node->balance == -2); if (node->right->balance < 1) rotate_left( node ); else if ( node->right->balance == 1) rotate_right_left(node); } // adjust_balance_right()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::begin | ( | ) |
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==().
{ if (m_tree == NULL) return iterator(NULL, true); else return lower_bound(); } // avl_base::begin()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::begin | ( | ) | const |
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.
{ if (m_tree == NULL) return const_iterator(NULL, true); else return lower_bound(); } // avl_base::begin()
bool claw::avl_base< K, Comp >::check_balance | ( | const avl_node_ptr | node | ) | const [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().
{ int pl=0, pr=0; if (node == NULL) return true; else { if (node->left) pl = node->left->depth(); if (node->right) pr = node->right->depth(); return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance) && check_balance(node->left) && check_balance(node->right); } } // check_balance()
bool claw::avl_base< K, Comp >::check_in_bounds | ( | const avl_node_ptr | node, | |
const K & | min, | |||
const K & | max | |||
) | const [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().
{ if (node == NULL) return true; else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) ) return (node->left == NULL) && check_in_bounds( node->right, node->key, max ); else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) ) return (node->right == NULL) && check_in_bounds( node->left, min, node->key ); else return s_key_less(node->key, max) && s_key_less(min, node->key) && check_in_bounds( node->left, min, node->key ) && check_in_bounds( node->right, node->key, max ); } // check_less_than()
void claw::avl_base< K, Comp >::clear | ( | ) |
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 [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().
{ bool valid = true; if (node != NULL) { if (node->father != NULL) { valid = (node->father->left == node) ^ (node->father->right == node); valid = valid && correct_descendant( node->left ) && correct_descendant( node->right ); } else valid = false; } return valid; } // 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().
{ return m_size == 0; } // avl_base::empty()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::end | ( | ) |
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==().
{ if (m_tree == NULL) return iterator(NULL, true); else return iterator(m_tree->upper_bound(), true); } // avl_base::end()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::end | ( | ) | const |
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().
{ if (m_tree == NULL) return const_iterator(NULL, true); else return const_iterator(m_tree->upper_bound(), true); } // avl_base::end()
void claw::avl_base< K, Comp >::erase | ( | const K & | key | ) |
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().
{ assert( validity_check() ); if (m_tree != NULL) recursive_delete( m_tree, key ); assert( validity_check() ); } // avl_base::erase()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find | ( | const K & | key | ) |
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().
{ return make_iterator( m_tree->find(key) ); } // avl_base::find()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find | ( | const K & | key | ) | const |
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().
{ return make_const_iterator( m_tree->find(key) ); } // avl_base::find()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_greater | ( | const K & | key | ) |
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().
{ return make_iterator( m_tree->find_nearest_greater(key) ); } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::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.
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().
{ return make_const_iterator( m_tree->find_nearest_greater(key) ); } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::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.
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().
{ return make_const_iterator( m_tree->find_nearest_lower(key) ); } // avl_base::find_nearest_lower()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_lower | ( | const K & | key | ) |
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().
{ return make_iterator( m_tree->find_nearest_lower(key) ); } // 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 | |||
) | [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().
{ avl_node_ptr* node; // node for search bool exists; // if this key already exists last_imbalanced = m_tree; node = & m_tree; node_father = NULL; exists = false; while ( ((*node) != NULL) && !exists ) { if ( (*node)->balance != 0 ) last_imbalanced = *node; // find next node if ( s_key_less(key, (*node)->key) ) { node_father = *node; node = & (*node)->left; } else if ( s_key_less((*node)->key, key) ) { node_father = *node; node = & (*node)->right; } else exists = true; } return node; } // find_node_reference()
void claw::avl_base< K, Comp >::insert | ( | Iterator | first, | |
Iterator | last | |||
) |
Add a range of items in the tree.
first | Iterator on the first item to add. | |
last | Iterator past the last item to add. |
Definition at line 971 of file avl_base.tpp.
References claw::avl_base< K, Comp >::insert().
{ for ( ; first!=last; ++first ) insert( *first ); } // avl_base::insert()
void claw::avl_base< K, Comp >::insert | ( | const K & | key | ) |
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().
{ assert( validity_check() ); if ( m_tree == NULL ) { m_tree = new avl_node(key); m_size = 1; } else insert_node(key); assert( validity_check() ); } // avl_base::insert()
void claw::avl_base< K, Comp >::insert_node | ( | const K & | key | ) | [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().
{ avl_node_ptr* new_node; avl_node_ptr node_father; avl_node_ptr last_imbalanced; avl_node_ptr last_imbalanced_father; assert(m_tree != NULL); new_node = find_node_reference(key, last_imbalanced, node_father ); if (*new_node == NULL) // this key isn't in use. Let's create a new node { *new_node = new avl_node(key); (*new_node)->father = node_father; ++m_size; last_imbalanced_father = last_imbalanced->father; // Update balance of the last imbalanced node update_balance( last_imbalanced, key ); // then adjust it to be in range [-1, 1] adjust_balance( last_imbalanced ); // pointer update after rotation if ( last_imbalanced_father == NULL ) { m_tree = last_imbalanced; m_tree->father = NULL; } else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key)) // left child last_imbalanced_father->left = last_imbalanced; else last_imbalanced_father->right = last_imbalanced; } } // insert_node()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::lower_bound | ( | ) |
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().
{ return make_iterator( m_tree->lower_bound() ); } // avl_base::lower_bound()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::lower_bound | ( | ) | const |
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().
{ return make_const_iterator( m_tree->lower_bound() ); } // 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 [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().
{ if (node != NULL) return const_iterator(node, false); else return end(); } // avl_base::make_const_iterator()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::make_iterator | ( | avl_node_ptr | node | ) | const [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 | |||
) | [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().
{ assert( (imbalance==1) || (imbalance==-1) ); assert( node != NULL ); node->balance += imbalance; switch(node->balance) { // balance == 0 so as it was != 0 before deletion // balance of the tree had changed case 0: return true; // balance == 2 so it must be 1 before deletion and node // was deleted in the right subtree // if after ajusting the balance is equal to 1, it means that // our subtree got back his old balance (so it's unchanged). // if it's equal to -1, it means that subtree now lean to the // otherside. But in those cases, depth didn't changed. case 2: adjust_balance_left(node); return node->balance == 0; // same thing but symetric case -2: adjust_balance_right(node); return node->balance == 0; default : return false; } } // new_balance()
bool claw::avl_base< K, Comp >::operator!= | ( | const avl_base< K, Comp > & | that | ) | const |
Disequality.
that | AVL top compare to. |
Definition at line 1254 of file avl_base.tpp.
{ return !( *this == that ); } // avl_base::operator!=()
bool claw::avl_base< K, Comp >::operator< | ( | const avl_base< K, Comp > & | that | ) | const |
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.
{ return std::lexicographical_compare ( begin(), end(), that.begin(), that.end(), s_key_less ); } // avl_base::operator<()
bool claw::avl_base< K, Comp >::operator<= | ( | const avl_base< K, Comp > & | that | ) | const |
Less or equal operator.
that | AVL top compare to. |
Definition at line 1288 of file avl_base.tpp.
{ return !( that < *this ); } // avl_base::operator<=()
claw::avl_base< K, Comp > & claw::avl_base< K, Comp >::operator= | ( | const avl_base< K, Comp > & | that | ) |
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.
bool claw::avl_base< K, Comp >::operator== | ( | const avl_base< K, Comp > & | that | ) | const |
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.
{ if (m_size != that.m_size) return false; else return std::equal( begin(), end(), that.begin(), s_key_less ); } // avl_base::operator==()
bool claw::avl_base< K, Comp >::operator> | ( | const avl_base< K, Comp > & | that | ) | const |
Greater than operator.
that | AVL top compare to. |
Definition at line 1277 of file avl_base.tpp.
{ return that < *this; } // avl_base::operator>()
bool claw::avl_base< K, Comp >::operator>= | ( | const avl_base< K, Comp > & | that | ) | const |
Greater or equal operator.
that | AVL top compare to. |
Definition at line 1299 of file avl_base.tpp.
{ return !( *this < that ); } // avl_base::operator>=()
bool claw::avl_base< K, Comp >::recursive_delete | ( | avl_node_ptr & | node, | |
const K & | key | |||
) | [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().
{ bool result = false; if ( node != NULL ) { // try to find the key in the left subtree if ( s_key_less(key, node->key) ) { if ( recursive_delete( node->left, key ) ) result = new_balance( node, -1 ); } // try to find the key in the right subtree else if ( s_key_less(node->key, key) ) { if ( recursive_delete( node->right, key ) ) result = new_balance( node, 1 ); } else // we got it ! { --m_size; result = recursive_delete_node( node ); } } return result; } // recursive_delete()
int claw::avl_base< K, Comp >::recursive_delete_max | ( | avl_node_ptr & | root, | |
avl_node_ptr | node | |||
) | [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().
{ assert(node!=NULL); assert(root!=NULL); if ( root->right == NULL ) // We have the maximum { // node have only a left subtree if any. // This subtree has one node, at most. avl_node_ptr left_subtree; node->key = root->key; left_subtree = root->left; if (left_subtree) left_subtree->father = root->father; root->clear(); delete root; // rise the left subtree root = left_subtree; // depth have changed return true; } else // try to find the max in the right subtree if ( recursive_delete_max( root->right, node ) ) { // depth of the subtree changed (ie. decreased) // so root's tree lean to the left ++(root->balance); if (root->balance == 2) // tree is leaning too much { // old balance was 1 adjust_balance_left( root ); return root->balance == 0; // Say if balance is changed } else // if balance is 0, it means that old root leant to the left // and so his depth changed. // The other value for balance is 1, in this case // depth didn't change. See recursive_delete_node code comments. return root->balance == 0; } else // depth of the subtree didn't change return false; } // recursive_delete_max()
bool claw::avl_base< K, Comp >::recursive_delete_node | ( | avl_node_ptr & | node | ) | [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().
{ assert( node != NULL ); if ( node->left == NULL) // this node doesn't have a lower descendant { // Get right subtree of current node avl_node_ptr right_subtree = node->right; if (right_subtree) right_subtree->father = node->father; // Free memory pointed by the current node node->clear(); delete node; // then rise the old right subtree node = right_subtree; return true; } else // this node has a lower descendant, let's get it if ( recursive_delete_max( node->left, node ) ) { // left subtree depth has decreased // so reajust balance (rem. balance is not changed by delete_max) --(node->balance); if ( node->balance == -2 ) { // old balance was -1 adjust_balance_right(node); return node->balance == 0; // tell if depth has changed } else if ( node->balance == 0 ) // node had at least one subtree and old balance - 1 == 0 // so old balance = 1 return true; else // node's balance is -1 // As node's balance is (old balance - 1), node's balance must be -1 // (otherwise old balance is 2, that's impossible) // So old balance is 0. // Moreover old node have at least a left subtree. It means that // old node had 2 subtrees and their depths were equals. // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1 // We deleted a node in left subtree and so right subtree is // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node) // => Node depth is unchanged. return false; } else // depth is unchanged return false; } // recursive_delete_node()
void claw::avl_base< K, Comp >::rotate_left | ( | avl_node_ptr & | node | ) | [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().
{ avl_node_ptr p; char old_node_balance; char old_subtree_balance; assert( node != NULL ); assert( node->right != NULL ); assert( (-2 <= node->balance) && (node->balance <= -1) ) ; assert( (-2 <= node->right->balance) && (node->right->balance <= 1) ); assert( (node->right->balance != -2) || (node->balance == -2) ); old_node_balance = node->balance; old_subtree_balance = node->right->balance; // rotate nodes p = node->right; p->father = node->father; node->right = p->left; if (p->left) p->left->father = node; p->left = node; node->father = p; node = p; // adjust balance switch(old_subtree_balance) { case -2 : // old_node_balance is -2 too. node->balance = 0; node->left->balance = 1; break; case -1 : node->balance = old_node_balance + 2; node->left->balance = old_node_balance + 2; break; case 0 : node->balance = 1; node->left->balance = old_node_balance + 1; break; case 1 : node->balance = 2; node->left->balance = old_node_balance + 1; break; } } // rotate_left()
void claw::avl_base< K, Comp >::rotate_left_right | ( | avl_node_ptr & | node | ) | [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().
{ assert( node != NULL ); rotate_left( node->left ); rotate_right( node ); } // rotate_left_right()
void claw::avl_base< K, Comp >::rotate_right | ( | avl_node_ptr & | node | ) | [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().
{ avl_node_ptr p; char old_node_balance; char old_subtree_balance; assert( node != NULL ); assert( node->left != NULL ); assert( (1 <= node->balance) && (node->balance <= 2) ) ; assert( (-1 <= node->left->balance) && (node->left->balance <= 2) ); assert( (node->left->balance != 2) || (node->balance == 2) ); old_node_balance = node->balance; old_subtree_balance = node->left->balance; // rotate nodes p = node->left; p->father = node->father; node->left = p->right; if (p->right) p->right->father = node; p->right = node; node->father = p; node = p; // adjust balance switch(old_subtree_balance) { case -1 : node->balance = -2; node->right->balance = old_node_balance - 1; break; case 0 : node->balance = -1; node->right->balance = old_node_balance - 1; break; case 1 : node->balance = old_node_balance - 2; node->right->balance = old_node_balance - 2; break; case 2 : // old_node_balance is 2 too. node->balance = 0; node->right->balance = - 1; break; } } // rotate_right()
void claw::avl_base< K, Comp >::rotate_right_left | ( | avl_node_ptr & | node | ) | [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().
{ assert( node != NULL ); rotate_right( node->right ); rotate_left( node ); } // 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().
{ return m_size; } // avl_base::size()
void claw::avl_base< K, Comp >::swap | ( | avl_base< K, Comp > & | that | ) |
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 | |||
) | [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().
{ assert(node != NULL); bool done = false; while (!done) if ( s_key_less(key, node->key) ) { ++node->balance; node = node->left; } else if ( s_key_less(node->key, key) ) { --node->balance; node = node->right; } else done = true; } // update_balance()
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::upper_bound | ( | ) |
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().
{ return make_iterator( m_tree->upper_bound() ); } // avl_base::upper_bound()
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::upper_bound | ( | ) | const |
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().
{ return make_const_iterator( m_tree->upper_bound() ); } // avl_base::upper_bound()
bool claw::avl_base< K, Comp >::validity_check | ( | ) | const [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().
{ bool valid = true; if (m_tree != NULL) { avl_node *node_min, *node_max; // get lower and higher bounds, hope they are correct for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left); for (node_max = m_tree; node_max->right!=NULL; node_max = node_max->right); valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key); valid = valid && check_in_bounds(m_tree->right, m_tree->key, node_max->key); valid = valid && (m_tree->father == NULL) && correct_descendant( m_tree->left ) && correct_descendant( m_tree->right ); } return valid && check_balance(m_tree); } // 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 [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().