Definition at line 68 of file avl.hpp.
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. | |
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< K, Comp >::avl_node > | super |
Private Member Functions | |
avl_node (const avl_node &that) | |
Copy constructor. |
typedef binary_node< typename claw::avl<K,Comp>::avl_node > claw::avl< K, Comp >::avl_node::super [private] |
claw::avl< 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.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl< 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< K, Comp >::avl_node::~avl_node | ( | ) | [inline] |
claw::avl< K, Comp >::avl_node * claw::avl< 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.tpp.
References claw::avl< K, Comp >::avl_node::avl_node(), claw::avl< K, Comp >::avl_node::balance, 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 >::avl(), and claw::avl< 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()
void claw::avl< K, Comp >::avl_node::del_tree | ( | ) | [inline] |
Delete current node and his subtrees.
Definition at line 97 of file avl.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
Referenced by claw::avl< K, Comp >::clear(), claw::avl< K, Comp >::operator=(), and claw::avl< K, Comp >::~avl().
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< K, Comp >::avl_node::depth | ( | ) | const [inline] |
Get the depth of a tree.
Definition at line 120 of file avl.tpp.
References claw::binary_node< U >::left, and claw::binary_node< U >::right.
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()
K claw::avl< K, Comp >::avl_node::key |
Node key.
Definition at line 75 of file avl.hpp.
Referenced by claw::avl< K, Comp >::check_in_bounds(), claw::avl< K, Comp >::avl_node::duplicate(), claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::recursive_delete(), claw::avl< K, Comp >::recursive_delete_max(), claw::avl< K, Comp >::update_balance(), and claw::avl< K, Comp >::validity_check().
char claw::avl< 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 81 of file avl.hpp.
Referenced by claw::avl< K, Comp >::adjust_balance(), claw::avl< K, Comp >::adjust_balance_left(), claw::avl< K, Comp >::adjust_balance_right(), claw::avl< K, Comp >::check_balance(), claw::avl< K, Comp >::avl_node::duplicate(), claw::avl< K, Comp >::new_balance(), claw::avl< K, Comp >::recursive_delete_max(), claw::avl< K, Comp >::recursive_delete_node(), claw::avl< K, Comp >::rotate_left(), claw::avl< K, Comp >::rotate_right(), and claw::avl< K, Comp >::update_balance().
avl_node* claw::avl< K, Comp >::avl_node::father |
Father of the node. Null if this node is root.
Definition at line 83 of file avl.hpp.
Referenced by claw::avl< K, Comp >::correct_descendant(), claw::avl< K, Comp >::avl_node::duplicate(), claw::avl< K, Comp >::insert_node(), claw::avl< K, Comp >::recursive_delete_max(), claw::avl< K, Comp >::recursive_delete_node(), claw::avl< K, Comp >::rotate_left(), claw::avl< K, Comp >::rotate_right(), and claw::avl< K, Comp >::validity_check().