Node of a binary search tree (AVL). More...
Public Member Functions | |
avl_node (const K &k) | |
AVL's node constructor. | |
~avl_node () | |
AVL's node destructor. | |
avl_node * | duplicate (unsigned int &count) const |
Duplicate node and his subtrees. | |
void | del_tree () |
Delete current node and his subtrees. | |
unsigned int | depth () const |
Get the depth of a tree. | |
avl_node * | find (const K &k) |
Get a pointer on the node of the tree with a specified key. | |
const avl_node * | find (const K &k) const |
Get a pointer on the node of the tree with a specified key. | |
avl_node * | 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 avl_node * | 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. | |
avl_node * | 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 avl_node * | 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. | |
avl_node * | lower_bound () |
Get a pointer on the lowest value of the tree. | |
const avl_node * | lower_bound () const |
Get a pointer on the lowest value of the tree. | |
avl_node * | upper_bound () |
Get a pointer on the greatest value of the tree. | |
const avl_node * | upper_bound () const |
Get a pointer on the greatest value of the tree. | |
avl_node * | prev () |
Get the node immediately before this. | |
const avl_node * | prev () const |
Get the node immediately before this. | |
avl_node * | next () |
Get the node immediately greater than this. | |
const avl_node * | next () const |
Get the node immediately greater than this. | |
Public Attributes | |
K | key |
Node key. | |
char | balance |
Balance of the node is -1, 0 or 1. Equals to the difference between left child depth and right child depth. | |
avl_node * | father |
Father of the node. Null if this node is root. | |
Private Types | |
typedef binary_node< typename claw::avl_base< K, Comp > ::avl_node > | super |
The type of the parent class. | |
Private Member Functions | |
avl_node (const avl_node &that) | |
Copy constructor. |
Node of a binary search tree (AVL).
Definition at line 65 of file avl_base.hpp.
typedef binary_node< typename claw::avl_base<K,Comp>::avl_node > claw::avl_base< K, Comp >::avl_node::super [private] |
The type of the parent class.
Definition at line 70 of file avl_base.hpp.
claw::avl_base< K, Comp >::avl_node::avl_node | ( | const K & | k | ) | [explicit] |
AVL's node constructor.
k | Value of the node |
Definition at line 40 of file avl_base.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::avl_node::duplicate().
: super(), key(k), balance(0), father(NULL) { assert(!super::left); assert(!super::right); } // avl_node::avl_node() [constructeur]
claw::avl_base< K, Comp >::avl_node::~avl_node | ( | ) |
AVL's node destructor.
Definition at line 52 of file avl_base.tpp.
{
} // avl_node::~avl_node() [destructeur]
claw::avl_base< K, Comp >::avl_node::avl_node | ( | const avl_node & | that | ) | [explicit, private] |
void claw::avl_base< K, Comp >::avl_node::del_tree | ( | ) |
Delete current node and his subtrees.
Definition at line 97 of file avl_base.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::clear(), claw::avl_base< K, Comp >::operator=(), and claw::avl_base< K, Comp >::~avl_base().
{ if (super::left) { delete super::left; super::left = NULL; } if (super::right) { delete super::right; super::right = NULL; } assert( !super::left ); assert( !super::right ); } // avl_node::del_tree
unsigned int claw::avl_base< K, Comp >::avl_node::depth | ( | ) | const |
Get the depth of a tree.
Definition at line 120 of file avl_base.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::check_balance().
{ unsigned int pl=0, pr=0; if (super::left) pl = super::left->depth(); if (super::right) pr = super::right->depth(); if (pl > pr) return 1 + pl; else return 1 + pr; } // avl_node::depth()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::duplicate | ( | unsigned int & | count | ) | const |
Duplicate node and his subtrees.
count | (out) Count of duplicated nodes. |
Definition at line 65 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::avl_node(), claw::avl_base< K, Comp >::avl_node::balance, 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 >::avl_base(), and claw::avl_base< K, Comp >::operator=().
{ avl_node* node_copy = new avl_node(key); ++count; node_copy->balance = balance; node_copy->father = NULL; if (super::left) { node_copy->left = super::left->duplicate(count); node_copy->left->father = node_copy; } else node_copy->left = NULL; if (super::right) { node_copy->right = super::right->duplicate(count); node_copy->right->father = node_copy; } else node_copy->right = NULL; return node_copy; } // avl_node::duplicate()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find | ( | const K & | key | ) |
Get a pointer on the node of the tree with a specified key.
key | Key to find. |
Definition at line 140 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 >::find().
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find | ( | const K & | key | ) | const |
Get a pointer on the node of the tree with a specified key.
key | Key to find. |
Definition at line 165 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.
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 191 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::avl_node::next(), and claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::find_nearest_greater().
{ bool ok; avl_node* node = this; avl_node* prev_node = NULL; ok = false; while (node && !ok) if ( avl_base<K, Comp>::s_key_less(key, node->key) ) { prev_node = node; node = node->left; } else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) { prev_node = node; node = node->right; } else ok = true; if (ok) return node->next(); else if (prev_node) { if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) ) return prev_node->next(); else return prev_node; } else return node; } // avl_base::find_nearest_greater()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 234 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::avl_node::next(), and claw::binary_node< U >::right.
{ bool ok; const avl_node* node = this; const avl_node* prev_node = NULL; ok = false; while (node && !ok) if ( avl_base<K, Comp>::s_key_less(key, node->key) ) { prev_node = node; node = node->left; } else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) { prev_node = node; node = node->right; } else ok = true; if (ok) return node->next(); else if (prev_node) { if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) ) return prev_node->next(); else return prev_node; } else return node; } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 277 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::avl_node::prev(), claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.
Referenced by claw::avl_base< K, Comp >::find_nearest_lower().
{ bool ok; avl_node* node = this; avl_node* prev_node = NULL; ok = false; while (node && !ok) if ( s_key_less(key, node->key) ) { prev_node = node; node = node->left; } else if ( s_key_less(node->key, key) ) { prev_node = node; node = node->right; } else ok = true; if (ok) return node->prev(); else if (prev_node) { if ( s_key_less(key, prev_node->key) ) return prev_node; else return prev_node->prev(); } else return node; } // avl_base::find_nearest_lower()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 320 of file avl_base.tpp.
References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::avl_node::prev(), claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.
{ bool ok; const avl_node* node = this; const avl_node* prev_node = NULL; ok = false; while (node && !ok) if ( s_key_less(key, node->key) ) { prev_node = node; node = node->left; } else if ( s_key_less(node->key, key) ) { prev_node = node; node = node->right; } else ok = true; if (ok) return node->prev(); else if (prev_node) { if ( s_key_less(key, prev_node->key) ) return prev_node; else return prev_node->prev(); } else return node; } // avl_base::find_nearest_lower()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::lower_bound | ( | ) | const |
Get a pointer on the lowest value of the tree.
Definition at line 378 of file avl_base.tpp.
References claw::binary_node< U >::left.
{ const avl_node* node = this; if (node) while (node->left) node = node->left; return node; } // avl_base::lower_bound()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::lower_bound | ( | ) |
Get a pointer on the lowest value of the tree.
Definition at line 361 of file avl_base.tpp.
References claw::binary_node< U >::left.
Referenced by claw::avl_base< K, Comp >::lower_bound().
{ avl_node* node = this; if (node) while (node->left) node = node->left; return node; } // avl_base::lower_bound()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next | ( | ) |
Get the node immediately greater than this.
Definition at line 429 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 >::avl_node::find_nearest_greater(), and claw::avl_base< K, Comp >::avl_iterator::operator++().
{ avl_node* result = this; // node have a right subtree : go to the min if (result->right != NULL) { result = result->right; while (result->left != NULL) result = result->left; } else { bool done = false; avl_node* previous_node = this; // get parent node while (result->father && !done) { if (result->father->left == result) done = true; result = result->father; } // came back from the max node to the root if (!done) result = previous_node; } return result; } // avl_iterator::avl_node::next()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next | ( | ) | const |
Get the node immediately greater than this.
Definition at line 469 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.
{ const avl_node* result = this; // node have a right subtree : go to the min if (result->right != NULL) { result = result->right; while (result->left != NULL) result = result->left; } else { bool done = false; const avl_node* previous_node = this; // get parent node while (result->father && !done) { if (result->father->left == result) done = true; result = result->father; } // came back from the max node to the root if (!done) result = previous_node; } return result; } // avl_iterator::avl_node::next()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev | ( | ) |
Get the node immediately before this.
Definition at line 509 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 >::avl_node::find_nearest_lower(), and claw::avl_base< K, Comp >::avl_iterator::operator--().
{ avl_node* result = this; // node have a left subtree : go to the max if (result->left != NULL) { result = result->left; while (result->right != NULL) result = result->right; } else { bool done = false; // get parent node while (result->father && !done) { if (result->father->right == result) done = true; result = result->father; } } return result; } // avl_iterator::avl_node::prev()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev | ( | ) | const |
Get the node immediately before this.
Definition at line 544 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.
{ const avl_node* result = this; // node have a left subtree : go to the max if (result->left != NULL) { result = result->left; while (result->right != NULL) result = result->right; } else { bool done = false; // get parent node while (result->father && !done) { if (result->father->right == result) done = true; result = result->father; } } return result; } // avl_iterator::avl_node::prev()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::upper_bound | ( | ) |
Get a pointer on the greatest value of the tree.
Definition at line 395 of file avl_base.tpp.
References claw::binary_node< U >::right.
Referenced by claw::avl_base< K, Comp >::end(), and claw::avl_base< K, Comp >::upper_bound().
{ avl_node* node = this; if (node) while (node->right) node = node->right; return node; } // avl_base::upper_bound()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::upper_bound | ( | ) | const |
Get a pointer on the greatest value of the tree.
Definition at line 412 of file avl_base.tpp.
References claw::binary_node< U >::right.
{ const avl_node* node = this; if (node) while (node->right) node = node->right; return node; } // avl_base::upper_bound()
char claw::avl_base< K, Comp >::avl_node::balance |
Balance of the node is -1, 0 or 1. Equals to the difference between left child depth and right child depth.
Definition at line 114 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::check_balance(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::new_balance(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::avl_base< K, Comp >::rotate_left(), claw::avl_base< K, Comp >::rotate_right(), and claw::avl_base< K, Comp >::update_balance().
avl_node* claw::avl_base< K, Comp >::avl_node::father |
Father of the node. Null if this node is root.
Definition at line 117 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::correct_descendant(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::avl_node::next(), claw::avl_base< K, Comp >::avl_node::prev(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::avl_base< K, Comp >::rotate_left(), claw::avl_base< K, Comp >::rotate_right(), and claw::avl_base< K, Comp >::validity_check().
K claw::avl_base< K, Comp >::avl_node::key |
Node key.
Definition at line 107 of file avl_base.hpp.
Referenced by claw::avl_base< K, Comp >::check_in_bounds(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::avl_iterator::operator*(), claw::avl_base< K, Comp >::avl_iterator::operator->(), claw::avl_base< K, Comp >::recursive_delete(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::update_balance(), and claw::avl_base< K, Comp >::validity_check().