#include <avl.hpp>
Each key appears only once. Nodes are sorted as left_child < node < right_child.
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.
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_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. | |
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. | |
Classes | |
class | avl_iterator |
AVL iterator. More... | |
class | avl_node |
Node of a binary search tree (AVL). More... |
typedef avl_node* claw::avl< K, Comp >::avl_node_ptr [private] |
typedef avl_node const* claw::avl< K, Comp >::const_avl_node_ptr [private] |
typedef const K claw::avl< K, Comp >::value_type |
typedef K claw::avl< K, Comp >::referent_type |
typedef const K& claw::avl< K, Comp >::const_reference |
typedef avl_iterator claw::avl< K, Comp >::const_iterator |
claw::avl< K, Comp >::avl | ( | const avl< K, Comp > & | that | ) | [inline, explicit] |
AVL copy constructor.
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]
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]
void claw::avl< K, Comp >::insert | ( | const K & | key | ) | [inline] |
Add a value in a tree.
key | Node 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()
void claw::avl< K, Comp >::insert | ( | Iterator | first, | |
Iterator | last | |||
) | [inline] |
Add a range of items in the tree.
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()
void claw::avl< K, Comp >::erase | ( | const K & | key | ) | [inline] |
Delete a value in a tree.
key | Node 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()
void claw::avl< K, Comp >::clear | ( | ) | [inline] |
Clear a tree.
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()
unsigned int claw::avl< K, Comp >::size | ( | ) | const [inline] |
Get the size of a 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()
bool claw::avl< K, Comp >::empty | ( | ) | const [inline] |
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::begin | ( | ) | const [inline] |
Get an iterator on the nodes of the tree.
Definition at line 512 of file avl.tpp.
References claw::avl< K, Comp >::lower_bound().
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::difference(), claw::math::ordered_set< K, Comp >::intersection(), claw::math::ordered_set< K, Comp >::join(), claw::automaton< State, Edge, StateComp, EdgeComp >::match(), and claw::automaton< State, Edge, StateComp, EdgeComp >::reachables().
00513 { 00514 return lower_bound(); 00515 } // avl::begin()
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::end | ( | ) | const [inline] |
Get an iterator after the end of the tree.
Definition at line 522 of file avl.tpp.
References claw::avl< K, Comp >::m_tree, and claw::binary_node< U >::right.
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::difference(), claw::avl< K, Comp >::find(), claw::avl< K, Comp >::find_nearest_greater(), claw::avl< K, Comp >::find_nearest_lower(), claw::arguments::get_bool(), claw::math::ordered_set< K, Comp >::intersection(), claw::math::ordered_set< K, Comp >::join(), claw::avl< K, Comp >::lower_bound(), claw::automaton< State, Edge, StateComp, EdgeComp >::match(), claw::arguments::parse(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), and claw::avl< K, Comp >::upper_bound().
00523 { 00524 const_avl_node_ptr node = m_tree; 00525 00526 if (node) 00527 while (node->right) 00528 node = node->right; 00529 00530 return const_iterator(node, true); 00531 } // avl::end()
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.
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()
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.
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()
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.
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()
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()
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()
claw::avl< K, Comp > & claw::avl< K, Comp >::operator= | ( | const avl< K, Comp > & | that | ) | [inline] |
Assignment operator.
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=()
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.
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 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()
bool claw::avl< 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 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()
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.
node | Node to check. |
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()
bool claw::avl< K, Comp >::validity_check | ( | ) | const [inline, private] |
This method will check orderliness in our trees : balance and order.
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()
void claw::avl< K, Comp >::rotate_right | ( | avl_node_ptr & | node | ) | [inline, private] |
Node right rotation.
node | Node to rotate. |
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()
void claw::avl< K, Comp >::rotate_left | ( | avl_node_ptr & | node | ) | [inline, private] |
Node left rotation.
node | Node to rotate. |
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()
void claw::avl< K, Comp >::rotate_left_right | ( | avl_node_ptr & | node | ) | [inline, private] |
Node left-right rotation.
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()
void claw::avl< K, Comp >::rotate_right_left | ( | avl_node_ptr & | node | ) | [inline, private] |
Node right-left rotation.
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()
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.
node | Root of the subtree to update. | |
key | Key of the just-added node. |
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()
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].
node | Node to adjust. |
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()
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].
node | Node to adjust. |
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()
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].
node | Node to adjust. |
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()
void claw::avl< K, Comp >::insert_node | ( | const K & | key | ) | [inline, private] |
Add a node to the tree.
key | Key for the new value. |
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()
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.
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 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()
bool claw::avl< 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 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()
bool claw::avl< 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. |
(imbalance==1) || (imbalance==-1)
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()
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).
node | Node to remove. |
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()
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.
root | Root of the tree in which find new values. | |
node | Node Wich gets values founded |
root != NULL
root is an AVL
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()
claw::avl< K, Comp >::key_less claw::avl< K, Comp >::s_key_less [inline, static, protected] |
Function object used to compare keys.
Definition at line 221 of file avl.hpp.
Referenced by claw::avl< K, Comp >::check_in_bounds(), claw::math::ordered_set< K, Comp >::contains(), claw::avl< K, Comp >::find(), claw::avl< K, Comp >::find_nearest_greater(), claw::avl< K, Comp >::find_nearest_lower(), claw::avl< K, Comp >::find_node_reference(), claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::recursive_delete(), and claw::avl< K, Comp >::update_balance().
Nodes count.
Definition at line 225 of file avl.hpp.
Referenced by claw::avl< K, Comp >::avl(), claw::avl< K, Comp >::clear(), claw::avl< K, Comp >::empty(), claw::avl< K, Comp >::insert(), claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::operator=(), claw::avl< K, Comp >::recursive_delete(), and claw::avl< K, Comp >::size().
avl_node_ptr claw::avl< K, Comp >::m_tree [private] |
Nodes.
Definition at line 228 of file avl.hpp.
Referenced by claw::avl< K, Comp >::avl(), claw::avl< K, Comp >::clear(), claw::avl< K, Comp >::end(), claw::avl< K, Comp >::erase(), claw::avl< K, Comp >::find(), claw::avl< K, Comp >::find_nearest_greater(), claw::avl< K, Comp >::find_nearest_lower(), claw::avl< K, Comp >::find_node_reference(), claw::avl< K, Comp >::insert(), claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::lower_bound(), claw::avl< K, Comp >::operator=(), claw::avl< K, Comp >::upper_bound(), claw::avl< K, Comp >::validity_check(), and claw::avl< K, Comp >::~avl().