#include <avltree.h>
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 > |
Definition at line 52 of file avltree.h.
typedef int16s AVL_tree_namespace::AVLNode< avlkey_t >::height_t [private] |
typedef AVLNode< avlkey_t >* AVL_tree_namespace::AVLNode< avlkey_t >::pnode_t [private] |
AVL_tree_namespace::AVLNode< avlkey_t >::AVLNode | ( | avlkey_t | key_val | ) | [inline] |
AVL_tree_namespace::AVLNode< avlkey_t >::~AVLNode | ( | ) | [inline] |
height_t AVL_tree_namespace::AVLNode< avlkey_t >::GetHeight | ( | void | ) | [inline] |
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::Initialize | ( | void | ) | [inline] |
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 }
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::PromoteLeft | ( | void | ) | [inline] |
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::PromoteRight | ( | void | ) | [inline] |
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 }
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 }
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 }
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 }
void AVL_tree_namespace::AVLNode< avlkey_t >::UpdateHeight | ( | void | ) | [inline] |
friend class AVLTree< avlkey_t > [friend] |
int8s AVL_tree_namespace::AVLNode< avlkey_t >::Balance |
height_t AVL_tree_namespace::AVLNode< avlkey_t >::Height |
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::LChild |
avlkey_t AVL_tree_namespace::AVLNode< avlkey_t >::NodeKey |
pnode_t AVL_tree_namespace::AVLNode< avlkey_t >::RChild |