00001 00002 // PROYECTO FIN DE CARRERA // 00003 // TÍTULO: Implementación de un Simulador de Redes de Acceso Pasivas en Omnet // 00004 // // 00005 // AUTOR: Jose Maria Robledo Saez // 00006 // TUTOR: Noemi Merayo Alvarez // 00007 // INGENIERÍA TÉCNICA DE TELECOMUNICACIONES, SISTEMAS DE TELECOMUNICACIÓN // 00008 // UNIVERSIDAD DE VALLADOLID // 00010 00031 #ifndef _AVL_AVLTREE_H_V001_INCLUDED_ 00032 #define _AVL_AVLTREE_H_V001_INCLUDED_ 00033 00034 #include "_types.h" 00035 00036 namespace AVL_tree_namespace { 00037 00038 template < class avlkey_t > class AVLNode; 00039 template < class avlkey_t > class AVLTree; 00040 00041 //#pragma inline_depth( 128 ) 00042 //#pragma inline_recursion( on ) 00043 00044 00045 00046 00047 /******************************************************************* 00048 ** CLASS: class AVLNode 00049 ** PURPOSE: Represents a node in an AVL tree 00050 ** @brief Represents a node in an AVL tree 00051 ********************************************************************/ 00052 template < class avlkey_t > class AVLNode 00053 { 00054 typedef AVLNode< avlkey_t >* pnode_t; 00055 typedef int16s height_t; 00056 00057 friend class AVLTree< avlkey_t >; 00058 00059 /*******************************************************************/ 00060 public: 00061 /*******************************************************************/ 00062 00063 int8s Balance; /* Node balance: height of right subtree 00064 minus height of left subtree */ 00065 00066 height_t Height; /* maximum distance to any leave */ 00067 00068 /***************************************************************/ 00069 inline height_t GetHeight( void ) { return Height; } 00070 /***************************************************************/ 00071 inline pnode_t Initialize(void) 00072 { 00073 LChild = NULL; 00074 RChild = NULL; 00075 Balance = 0; 00076 Height = 0; 00077 return this; 00078 } 00079 00080 /*************************************************************** 00081 ** METHOD: void UpdateHeight( void ) 00082 ** PURPOSE: Recalcilates height and balance of given node 00083 ** RETURN VALUE: 00084 ****************************************************************/ 00085 inline void UpdateHeight( void ) 00086 { 00087 height_t LHeight = LChild? LChild->Height : (height_t) -1; 00088 height_t RHeight = RChild? RChild->Height : (height_t) -1; 00089 00090 Height = MAX<height_t>( LHeight, RHeight ) + 1; 00091 Balance = (int8s)(RHeight - LHeight); 00092 } 00093 00094 /*************************************************************** 00095 ** METHOD: pnode_t PromoteRight( void ) 00096 ** PURPOSE: Makes right child the parent (ratation left) 00097 ** RETURN VALUE: new root of the subtree 00098 ****************************************************************/ 00099 inline pnode_t PromoteRight( void ) 00100 { 00101 pnode_t pNode = RChild; 00102 RChild = pNode->LChild; 00103 pNode->LChild = this; 00104 00105 this ->UpdateHeight(); 00106 pNode->UpdateHeight(); 00107 00108 return pNode; 00109 } 00110 00111 /*************************************************************** 00112 ** METHOD: pnode_t PromoteLeft( void ) 00113 ** PURPOSE: Makes left child the parent (ratation right) 00114 ** RETURN VALUE: new root of the subtree 00115 ****************************************************************/ 00116 inline pnode_t PromoteLeft( void ) 00117 { 00118 pnode_t pNode = LChild; 00119 LChild = pNode->RChild; 00120 pNode->RChild = this; 00121 00122 this ->UpdateHeight(); 00123 pNode->UpdateHeight(); 00124 00125 return pNode; 00126 } 00127 00128 /*************************************************************** 00129 ** METHOD: pnode_t RepairBalance( void ) 00130 ** PURPOSE: Updates node's height and performs balancing, 00131 ** if necessary 00132 ** RETURN VALUE: new root of the subtree 00133 ****************************************************************/ 00134 inline pnode_t RepairBalance( void ) 00135 { 00136 UpdateHeight(); 00137 00138 if( Balance < -1 ) 00139 { 00140 /* if imbalance is due to internal branch, do double promotion */ 00141 if( LChild->Balance > 0 ) LChild = LChild->PromoteRight(); 00142 return PromoteLeft(); 00143 } 00144 00145 if( Balance > 1 ) 00146 { 00147 /* if imbalance is due to internal branch, do double promotion */ 00148 if( RChild->Balance < 0 ) RChild = RChild->PromoteLeft(); 00149 return PromoteRight(); 00150 } 00151 00152 return this; 00153 } 00154 00155 /*************************************************************** 00156 ** METHOD: pnode_t InsertNode( pnode_t pNode ) 00157 ** PURPOSE: Inserts node into a subtree rooted at the current node 00158 ** ARGUMENTS: pNode - node to insert 00159 ** RETURN VALUE: new root of the subtree 00160 ****************************************************************/ 00161 inline pnode_t InsertNode( pnode_t pNode ) 00162 { 00163 if( pNode->NodeKey > NodeKey ) 00164 RChild = RChild? RChild->InsertNode( pNode ): pNode->Initialize(); 00165 00166 else //if( pNode->NodeKey <= NodeKey ) 00167 LChild = LChild? LChild->InsertNode( pNode ): pNode->Initialize(); 00168 00169 return RepairBalance(); 00170 } 00171 00172 /*************************************************************** 00173 ** METHOD: pnode_t RemoveNode( pnode_t pNode, BOOL* result ) 00174 ** PURPOSE: Removes node from a subtree rooted at the current node 00175 ** 00176 ** ARGUMENTS: pNode - node to remove (never NULL) 00177 ** result - placeholder for the boolean indicating 00178 ** whether given node was found in the tree 00179 ** and removed or not 00180 ** 00181 ** RETURN VALUE: new root of the subtree 00182 ****************************************************************/ 00183 inline pnode_t RemoveNode( pnode_t pNode, BOOL* result ) 00184 { 00185 if( pNode == this ) 00186 { 00187 if( !LChild ) return RChild; 00188 if( !RChild ) return LChild; 00189 00190 /* swap pNode with the right end of its left sub-AVLTree */ 00191 pnode_t ptr, left_subroot; 00192 00193 left_subroot = LChild->RemoveRightEnd( &ptr ); 00194 ptr->LChild = left_subroot; 00195 ptr->RChild = RChild; 00196 00197 *result = TRUE; 00198 return ptr->RepairBalance(); 00199 } 00200 00201 if( pNode->NodeKey > NodeKey && RChild ) 00202 { 00203 RChild = RChild->RemoveNode( pNode, result ); 00204 return RepairBalance(); 00205 } 00206 00207 if( pNode->NodeKey <= NodeKey && LChild ) 00208 { 00209 LChild = LChild->RemoveNode( pNode, result ); 00210 return RepairBalance(); 00211 } 00212 } 00213 00214 /*************************************************************** 00215 ** METHOD: pnode_t RemoveLeftEnd( pnode_t* ppNode ) 00216 ** PURPOSE: Removes the leftmost (smallest) node from a 00217 ** subtree rooted at the current node 00218 ** 00219 ** ARGUMENTS: pNode - placeholder for the address of the removed node 00220 ** 00221 ** RETURN VALUE: new root of the subtree 00222 ****************************************************************/ 00223 inline pnode_t RemoveLeftEnd( pnode_t* ppNode ) 00224 { 00225 if( !LChild ) /* end of recursion */ 00226 { 00227 *ppNode = this; 00228 return RChild; 00229 } 00230 LChild = LChild->RemoveLeftEnd( ppNode ); 00231 return RepairBalance(); 00232 } 00233 00234 /*************************************************************** 00235 ** METHOD: pnode_t RemoveRightEnd( pnode_t* ppNode ) 00236 ** PURPOSE: Removes the rightmost (largest) node from a 00237 ** subtree rooted at the current node 00238 ** 00239 ** ARGUMENTS: pNode - placeholder for the address of the removed node 00240 ** 00241 ** RETURN VALUE: new root of the subtree 00242 ****************************************************************/ 00243 inline pnode_t RemoveRightEnd( pnode_t* ppNode ) 00244 { 00245 if( !RChild ) /* end of recursion */ 00246 { 00247 *ppNode = this; 00248 return LChild; 00249 } 00250 RChild = RChild->RemoveRightEnd( ppNode ); 00251 return RepairBalance(); 00252 } 00253 00254 00255 public: 00256 00257 00258 pnode_t LChild; /* Left child */ 00259 pnode_t RChild; /* Right child */ 00260 avlkey_t NodeKey; /* */ 00261 00262 00263 public: 00264 00265 AVLNode( avlkey_t key_val ) { Initialize(); NodeKey = key_val; } 00266 /* virtual */ ~AVLNode() {} 00267 00268 }; 00269 00270 00271 00272 00273 00274 /******************************************************************* 00275 ** CLASS: class AVLTree 00276 ** PURPOSE: 00277 public: 00278 00279 @brief Represents AVLTree composed of AVLNodes 00280 ********************************************************************/ 00281 template < class avlkey_t > class AVLTree 00282 { 00283 typedef AVLNode< avlkey_t >* pnode_t; 00284 00285 00286 public: 00287 00288 pnode_t pRoot; /* root node of the tree */ 00289 int32u Count; /* number of nodes in the tree */ 00290 00291 public: 00292 00293 00294 AVLTree() 00295 { 00296 pRoot = NULL; 00297 Count = 0; 00298 } 00299 00300 virtual ~AVLTree() {} 00301 00302 /***************************************************************/ 00303 inline int32u GetCount(void) const { return Count; } 00304 00305 /***************************************************************/ 00306 inline void AddNode( pnode_t pNode ) 00307 { 00308 if( pNode ) 00309 { 00310 pRoot = ( pRoot )? pRoot->InsertNode( pNode ): pNode->Initialize(); 00311 Count++; 00312 } 00313 } 00314 /***************************************************************/ 00315 inline BOOL RemoveNode( pnode_t pNode ) 00316 { 00317 BOOL result = FALSE; 00318 if( pRoot && pNode ) pRoot = pRoot->RemoveNode( pNode, &result ); 00319 if( result ) Count--; 00320 return result; 00321 } 00322 /***************************************************************/ 00323 inline pnode_t RemoveHead( ) 00324 { 00325 pnode_t pNode = NULL; 00326 if( pRoot ) pRoot = pRoot->RemoveLeftEnd( &pNode ); 00327 if( pNode ) Count--; 00328 return pNode; 00329 } 00330 /***************************************************************/ 00331 inline pnode_t RemoveTail( ) 00332 { 00333 //NODE_t* pNode = NULL; 00334 pnode_t pNode = NULL; 00335 00336 if( pRoot ) pRoot = pRoot->RemoveRightEnd( &pNode ); 00337 if( pNode ) Count--; 00338 return pNode; 00339 } 00340 }; 00341 00342 00343 00344 00345 }; // namespace AVL_tree_namespace 00346 00347 namespace AVL = AVL_tree_namespace; 00348 namespace AVLTREE = AVL_tree_namespace; 00349 00350 #endif // _AVL_AVLTREE_H_V001_INCLUDED_