claw::avl< K, Comp >::avl_node Class Reference

Inheritance diagram for claw::avl< K, Comp >::avl_node:

claw::binary_node< U >

List of all members.


Detailed Description

template<class K, class Comp = std::less<K>>
class claw::avl< K, Comp >::avl_node

Node of a binary search tree (AVL).

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_nodeduplicate (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

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_nodefather
 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.

Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef binary_node< typename claw::avl<K,Comp>::avl_node > claw::avl< K, Comp >::avl_node::super [private]

Definition at line 71 of file avl.hpp.


Constructor & Destructor Documentation

template<class K, class Comp>
claw::avl< K, Comp >::avl_node::avl_node ( const K &  k  )  [inline, explicit]

AVL's node constructor.

Parameters:
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]

template<class K, class Comp>
claw::avl< K, Comp >::avl_node::~avl_node (  )  [inline]

AVL's node destructor.

Definition at line 52 of file avl.tpp.

00053 {
00054 
00055 } // avl_node::~avl_node() [destructeur]

template<class K, class Comp>
claw::avl< K, Comp >::avl_node::avl_node ( const avl_node that  )  [inline, explicit, private]

Copy constructor.

Parameters:
that Node to copy from.
Remarks:
Shouldn't be use.

Definition at line 147 of file avl.tpp.

00148   : super(that), key(that.key), balance(that.balance), father(NULL) 
00149 {
00150   assert(0);
00151 } // avl_node::depth()


Member Function Documentation

template<class K, class Comp>
claw::avl< K, Comp >::avl_node * claw::avl< K, Comp >::avl_node::duplicate ( unsigned int &  count  )  const [inline]

Duplicate node and his subtrees.

Parameters:
count (out) Count of duplicated nodes.
Remarks:
Count isn't initialized. You should call duplicate with count = 0.

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()

template<class K, class Comp>
void claw::avl< K, Comp >::avl_node::del_tree (  )  [inline]

Delete current node and his subtrees.

Postcondition:
left == NULL && right == NULL

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

template<class K, class Comp>
unsigned int claw::avl< K, Comp >::avl_node::depth (  )  const [inline]

Get the depth of a tree.

Remarks:
For validity check.
Returns:
1 + max( this->left->depth(), this->right->depth() )

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()


Member Data Documentation

template<class K, class Comp = std::less<K>>
K claw::avl< K, Comp >::avl_node::key

template<class K, class Comp = std::less<K>>
char claw::avl< K, Comp >::avl_node::balance

template<class K, class Comp = std::less<K>>
avl_node* claw::avl< K, Comp >::avl_node::father


The documentation for this class was generated from the following files:

Generated on Thu May 22 21:07:37 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.5