AVL_tree_namespace::AVLNode< avlkey_t > Class Template Reference

#include <avltree.h>

Inheritance diagram for AVL_tree_namespace::AVLNode< avlkey_t >:

GEN::Stream GEN::StreamCBR GEN::StreamExpon GEN::StreamPareto

List of all members.

Public Member Functions

height_t GetHeight (void)
pnode_t Initialize (void)
void UpdateHeight (void)
pnode_t PromoteRight (void)
pnode_t PromoteLeft (void)
pnode_t RepairBalance (void)
pnode_t InsertNode (pnode_t pNode)
pnode_t RemoveNode (pnode_t pNode, BOOL *result)
pnode_t RemoveLeftEnd (pnode_t *ppNode)
pnode_t RemoveRightEnd (pnode_t *ppNode)
 AVLNode (avlkey_t key_val)
 ~AVLNode ()

Public Attributes

int8s Balance
height_t Height
pnode_t LChild
pnode_t RChild
avlkey_t NodeKey

Private Types

typedef AVLNode< avlkey_t > * pnode_t
typedef int16s height_t

Friends

class AVLTree< avlkey_t >


Detailed Description

template<class avlkey_t>
class AVL_tree_namespace::AVLNode< avlkey_t >

Definition at line 52 of file avltree.h.


Member Typedef Documentation

template<class avlkey_t >
typedef int16s AVL_tree_namespace::AVLNode< avlkey_t >::height_t [private]

Definition at line 55 of file avltree.h.

template<class avlkey_t >
typedef AVLNode< avlkey_t >* AVL_tree_namespace::AVLNode< avlkey_t >::pnode_t [private]

Definition at line 54 of file avltree.h.


Constructor & Destructor Documentation

template<class avlkey_t >
AVL_tree_namespace::AVLNode< avlkey_t >::AVLNode ( avlkey_t  key_val  )  [inline]

Definition at line 265 of file avltree.h.

00265 { Initialize(); NodeKey = key_val; }

template<class avlkey_t >
AVL_tree_namespace::AVLNode< avlkey_t >::~AVLNode (  )  [inline]

Definition at line 266 of file avltree.h.

00266 {}


Member Function Documentation

template<class avlkey_t >
height_t AVL_tree_namespace::AVLNode< avlkey_t >::GetHeight ( void   )  [inline]

Definition at line 69 of file avltree.h.

00069 { return Height; }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::Initialize ( void   )  [inline]

Definition at line 71 of file avltree.h.

00072     {
00073         LChild  = NULL;
00074         RChild  = NULL;
00075         Balance = 0;
00076         Height  = 0;
00077         return this;
00078     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::InsertNode ( pnode_t  pNode  )  [inline]

Definition at line 161 of file avltree.h.

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     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::PromoteLeft ( void   )  [inline]

Definition at line 116 of file avltree.h.

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     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::PromoteRight ( void   )  [inline]

Definition at line 99 of file avltree.h.

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     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RemoveLeftEnd ( pnode_t ppNode  )  [inline]

Definition at line 223 of file avltree.h.

00224     {
00225         if( !LChild )  /* end of recursion */
00226         {
00227             *ppNode = this;
00228             return RChild;
00229         }
00230         LChild = LChild->RemoveLeftEnd( ppNode );
00231         return RepairBalance();
00232     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RemoveNode ( pnode_t  pNode,
BOOL *  result 
) [inline]

Definition at line 183 of file avltree.h.

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     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RemoveRightEnd ( pnode_t ppNode  )  [inline]

Definition at line 243 of file avltree.h.

00244     {
00245         if( !RChild )  /* end of recursion */
00246         {
00247             *ppNode = this;
00248             return LChild;
00249         }
00250         RChild = RChild->RemoveRightEnd( ppNode );
00251         return RepairBalance();
00252     }

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RepairBalance ( void   )  [inline]

Definition at line 134 of file avltree.h.

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     }

template<class avlkey_t >
void AVL_tree_namespace::AVLNode< avlkey_t >::UpdateHeight ( void   )  [inline]

Definition at line 85 of file avltree.h.

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     }


Friends And Related Function Documentation

template<class avlkey_t >
friend class AVLTree< avlkey_t > [friend]

Definition at line 57 of file avltree.h.


Member Data Documentation

template<class avlkey_t >
int8s AVL_tree_namespace::AVLNode< avlkey_t >::Balance

Definition at line 63 of file avltree.h.

template<class avlkey_t >
height_t AVL_tree_namespace::AVLNode< avlkey_t >::Height

Definition at line 66 of file avltree.h.

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::LChild

Definition at line 258 of file avltree.h.

template<class avlkey_t >
avlkey_t AVL_tree_namespace::AVLNode< avlkey_t >::NodeKey

Definition at line 260 of file avltree.h.

template<class avlkey_t >
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RChild

Definition at line 259 of file avltree.h.


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

Generated on Thu Nov 28 14:47:25 2013 for red_wireless by  doxygen 1.5.7.1