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 | ) | [inline, 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().
00041 : super(), key(k), balance(0), father(NULL) 00042 { 00043 assert(!super::left); 00044 assert(!super::right); 00045 } // avl_node::avl_node() [constructeur]
claw::avl_base< K, Comp >::avl_node::~avl_node | ( | ) | [inline] |
AVL's node destructor.
Definition at line 52 of file avl_base.tpp.
claw::avl_base< K, Comp >::avl_node::avl_node | ( | const avl_node & | that | ) | [inline, explicit, private] |
void claw::avl_base< K, Comp >::avl_node::del_tree | ( | ) | [inline] |
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().
00098 { 00099 if (super::left) 00100 { 00101 delete super::left; 00102 super::left = NULL; 00103 } 00104 if (super::right) 00105 { 00106 delete super::right; 00107 super::right = NULL; 00108 } 00109 assert( !super::left ); 00110 assert( !super::right ); 00111 } // avl_node::del_tree
unsigned int claw::avl_base< K, Comp >::avl_node::depth | ( | ) | const [inline] |
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().
00121 { 00122 unsigned int pl=0, pr=0; 00123 00124 if (super::left) pl = super::left->depth(); 00125 if (super::right) pr = super::right->depth(); 00126 00127 if (pl > pr) 00128 return 1 + pl; 00129 else 00130 return 1 + pr; 00131 } // avl_node::depth()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::duplicate | ( | unsigned int & | count | ) | const [inline] |
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=().
00066 { 00067 avl_node* node_copy = new avl_node(key); 00068 ++count; 00069 node_copy->balance = balance; 00070 node_copy->father = NULL; 00071 00072 if (super::left) 00073 { 00074 node_copy->left = super::left->duplicate(count); 00075 node_copy->left->father = node_copy; 00076 } 00077 else 00078 node_copy->left = NULL; 00079 00080 if (super::right) 00081 { 00082 node_copy->right = super::right->duplicate(count); 00083 node_copy->right->father = node_copy; 00084 } 00085 else 00086 node_copy->right = NULL; 00087 00088 return node_copy; 00089 } // avl_node::duplicate()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find | ( | const K & | key | ) | const [inline] |
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.
00166 { 00167 bool ok; 00168 const avl_node* node = this; 00169 00170 ok = false; 00171 00172 while (node && !ok) 00173 if ( avl_base<K, Comp>::s_key_less(key, node->key) ) 00174 node = node->left; 00175 else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) 00176 node = node->right; 00177 else 00178 ok = true; 00179 00180 return node; 00181 } // avl_base::avl_node::find()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find | ( | const K & | key | ) | [inline] |
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().
00141 { 00142 bool ok; 00143 avl_node* node = this; 00144 00145 ok = false; 00146 00147 while (node && !ok) 00148 if ( avl_base<K, Comp>::s_key_less(key, node->key) ) 00149 node = node->left; 00150 else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) 00151 node = node->right; 00152 else 00153 ok = true; 00154 00155 return node; 00156 } // avl_base::avl_node::find()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 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.
00235 { 00236 bool ok; 00237 const avl_node* node = this; 00238 const avl_node* prev_node = NULL; 00239 00240 ok = false; 00241 00242 while (node && !ok) 00243 if ( avl_base<K, Comp>::s_key_less(key, node->key) ) 00244 { 00245 prev_node = node; 00246 node = node->left; 00247 } 00248 else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) 00249 { 00250 prev_node = node; 00251 node = node->right; 00252 } 00253 else 00254 ok = true; 00255 00256 if (ok) 00257 return node->next(); 00258 else if (prev_node) 00259 { 00260 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) ) 00261 return prev_node->next(); 00262 else 00263 return prev_node; 00264 } 00265 else 00266 return node; 00267 } // avl_base::find_nearest_greater()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find_nearest_greater | ( | const K & | key | ) | [inline] |
Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
key | Key to find. |
Definition at line 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().
00192 { 00193 bool ok; 00194 avl_node* node = this; 00195 avl_node* prev_node = NULL; 00196 00197 ok = false; 00198 00199 while (node && !ok) 00200 if ( avl_base<K, Comp>::s_key_less(key, node->key) ) 00201 { 00202 prev_node = node; 00203 node = node->left; 00204 } 00205 else if ( avl_base<K, Comp>::s_key_less(node->key, key) ) 00206 { 00207 prev_node = node; 00208 node = node->right; 00209 } 00210 else 00211 ok = true; 00212 00213 if (ok) 00214 return node->next(); 00215 else if (prev_node) 00216 { 00217 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) ) 00218 return prev_node->next(); 00219 else 00220 return prev_node; 00221 } 00222 else 00223 return node; 00224 } // avl_base::find_nearest_greater()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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 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.
00321 { 00322 bool ok; 00323 const avl_node* node = this; 00324 const avl_node* prev_node = NULL; 00325 00326 ok = false; 00327 00328 while (node && !ok) 00329 if ( s_key_less(key, node->key) ) 00330 { 00331 prev_node = node; 00332 node = node->left; 00333 } 00334 else if ( s_key_less(node->key, key) ) 00335 { 00336 prev_node = node; 00337 node = node->right; 00338 } 00339 else 00340 ok = true; 00341 00342 if (ok) 00343 return node->prev(); 00344 else if (prev_node) 00345 { 00346 if ( s_key_less(key, prev_node->key) ) 00347 return prev_node; 00348 else 00349 return prev_node->prev(); 00350 } 00351 else 00352 return node; 00353 } // avl_base::find_nearest_lower()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find_nearest_lower | ( | const K & | key | ) | [inline] |
Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
key | Key to find. |
Definition at line 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().
00278 { 00279 bool ok; 00280 avl_node* node = this; 00281 avl_node* prev_node = NULL; 00282 00283 ok = false; 00284 00285 while (node && !ok) 00286 if ( s_key_less(key, node->key) ) 00287 { 00288 prev_node = node; 00289 node = node->left; 00290 } 00291 else if ( s_key_less(node->key, key) ) 00292 { 00293 prev_node = node; 00294 node = node->right; 00295 } 00296 else 00297 ok = true; 00298 00299 if (ok) 00300 return node->prev(); 00301 else if (prev_node) 00302 { 00303 if ( s_key_less(key, prev_node->key) ) 00304 return prev_node; 00305 else 00306 return prev_node->prev(); 00307 } 00308 else 00309 return node; 00310 } // avl_base::find_nearest_lower()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::lower_bound | ( | ) | const [inline] |
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.
00379 { 00380 const avl_node* node = this; 00381 00382 if (node) 00383 while (node->left) 00384 node = node->left; 00385 00386 return node; 00387 } // avl_base::lower_bound()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::lower_bound | ( | ) | [inline] |
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().
00362 { 00363 avl_node* node = this; 00364 00365 if (node) 00366 while (node->left) 00367 node = node->left; 00368 00369 return node; 00370 } // avl_base::lower_bound()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next | ( | ) | const [inline] |
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.
00470 { 00471 const avl_node* result = this; 00472 00473 // node have a right subtree : go to the min 00474 if (result->right != NULL) 00475 { 00476 result = result->right; 00477 00478 while (result->left != NULL) 00479 result = result->left; 00480 } 00481 else 00482 { 00483 bool done = false; 00484 const avl_node* previous_node = this; 00485 00486 // get parent node 00487 while (result->father && !done) 00488 { 00489 if (result->father->left == result) 00490 done = true; 00491 00492 result = result->father; 00493 } 00494 00495 // came back from the max node to the root 00496 if (!done) 00497 result = previous_node; 00498 } 00499 00500 return result; 00501 } // avl_iterator::avl_node::next()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next | ( | ) | [inline] |
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++().
00430 { 00431 avl_node* result = this; 00432 00433 // node have a right subtree : go to the min 00434 if (result->right != NULL) 00435 { 00436 result = result->right; 00437 00438 while (result->left != NULL) 00439 result = result->left; 00440 } 00441 else 00442 { 00443 bool done = false; 00444 avl_node* previous_node = this; 00445 00446 // get parent node 00447 while (result->father && !done) 00448 { 00449 if (result->father->left == result) 00450 done = true; 00451 00452 result = result->father; 00453 } 00454 00455 // came back from the max node to the root 00456 if (!done) 00457 result = previous_node; 00458 } 00459 00460 return result; 00461 } // avl_iterator::avl_node::next()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev | ( | ) | const [inline] |
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.
00545 { 00546 const avl_node* result = this; 00547 00548 // node have a left subtree : go to the max 00549 if (result->left != NULL) 00550 { 00551 result = result->left; 00552 00553 while (result->right != NULL) 00554 result = result->right; 00555 } 00556 else 00557 { 00558 bool done = false; 00559 00560 // get parent node 00561 while (result->father && !done) 00562 { 00563 if (result->father->right == result) 00564 done = true; 00565 00566 result = result->father; 00567 } 00568 } 00569 00570 return result; 00571 } // avl_iterator::avl_node::prev()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev | ( | ) | [inline] |
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--().
00510 { 00511 avl_node* result = this; 00512 00513 // node have a left subtree : go to the max 00514 if (result->left != NULL) 00515 { 00516 result = result->left; 00517 00518 while (result->right != NULL) 00519 result = result->right; 00520 } 00521 else 00522 { 00523 bool done = false; 00524 00525 // get parent node 00526 while (result->father && !done) 00527 { 00528 if (result->father->right == result) 00529 done = true; 00530 00531 result = result->father; 00532 } 00533 } 00534 00535 return result; 00536 } // avl_iterator::avl_node::prev()
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::upper_bound | ( | ) | const [inline] |
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.
00413 { 00414 const avl_node* node = this; 00415 00416 if (node) 00417 while (node->right) 00418 node = node->right; 00419 00420 return node; 00421 } // avl_base::upper_bound()
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::upper_bound | ( | ) | [inline] |
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().
00396 { 00397 avl_node* node = this; 00398 00399 if (node) 00400 while (node->right) 00401 node = node->right; 00402 00403 return node; 00404 } // 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().