My aa tree class has a segment memory fault after the second insertion into the class. Recursion would of been easier, but I took a non-recursive implementation for the class.
This is the whole code
I narrow where the fault lies at skew function. Maybe, I should just turn the function into a #define macro? If I stick to the recursive implementation would it be a significant lack of performance for updating sprite information for my game.Code:template <class data> struct AANODE { unsigned int level; unsigned int priority; data * hold; AANODE<data> * left; AANODE<data> * right; }; template <class data> class AATREE { AANODE<data> * tree; unsigned int numofnodes; void skew(AANODE<data> *& Branch) { if( Branch->left->level== Branch->level && Branch->level != 0 ) { AANODE<data> * tempt = Branch->left; Branch->left = tempt->right; tempt->right = Branch; Branch = tempt; } } void split(AANODE<data> *& Branch) { if( Branch->right->right->level == Branch->level &&Branch->level != 0) { AANODE<data> * tempt = Branch->right; Branch->right = tempt->left; Branch->left = Branch; Branch = tempt; ++Branch->level; } } public: AATREE(void){ tree = 0; } void insert( data * item, unsigned int Priority ) { if(tree == 0) { tree = new AANODE<data>; tree->hold = item; tree->level = 1; tree->right = tree->left = 0; tree->priority = Priority; } else { AANODE<data> * it = tree; AANODE<data> * array[60] ; int top = 0, dir = 0; do { array[top++] = it; dir = it->priority < Priority; if( dir == 0) { if( it->left == 0) break; else it = it->left; } if(dir == 1) { if(it->right == 0) break; else it = it->right; } }while(1); if( dir == 0) { it->left = new AANODE<data>; it->left->hold = item; it->left->level = 1; it->left->right = it->left->left = 0; it->priority = Priority; } if( dir == 1) { it->right = new AANODE<data>; it->right->hold = item; it->right->level = 1; it->right->right = it->right->left = 0; it->priority = Priority; } cout<<"enters"<<endl; while( --top >= 0) { if( top!= 0) dir = array[top - 1]->right == array[top]; skew(array[top]) ; split(array[top]); cout<<"here"<<endl; if(top != 0) { if( dir == 0) array[top - 1]->left = array[top]; if(dir == 1) array[top - 1]->right = array[top]; } else tree = array[top]; --top; } cout<<"exits"<<endl; } } void remove(unsigned int Priority) { if( tree != 0) { AANODE<data> * it = tree; AANODE<data> * array[200]; int top = 0, dir = 0; do { array[top++] = it; if( it = 0) return; else if(Priority == it->priority) break; dir = it->priority < Priority; if( dir == 0) it = it->left; if(dir == 1) it = it->right; }while(1); if(it->left == 0 || it->right ==0) { int dir2 = it->left == 0; if( --top!= 0) { if( dir == 0) { if( dir2 == 0) array[top - 1]->left = it->left; if( dir2 == 1 ) array[top - 1]->left = it->right; } if(dir == 1) { if( dir2 == 0) array[top - 1]->right = it->left; if( dir2 == 1 ) array[top - 1]->right = it->right; } } else tree = it->right; } else { AANODE<data> * heir = it->right; AANODE<data> * prev = it; while( heir->left != 0) { array[top++] = prev = heir; heir = heir->left; } it->data = heir->data; bool side = (prev == it); if( side == 0) prev->left = heir->right; else prev->right = heir->right; } while(--top >= 0 ) { if( top != 0 ) dir = array[top - 1]->right == array[top]; if( (array[top]->left->level < array[top]->level - 1) || (array[top]->right->level < array[top]->level -1) ) { if(array[top]->right->level > --array[top]->level) array[top]->right->level = array[top]->level; skew(array[top]); skew(array[top]->right); skew(array[top]->right->right); split(array[top]); split(array[top]->right); } } if( top!=0) { if( dir == 0) array[top - 1]->left = array[top]; if( dir == 1 ) array[top - 1]->right = array[top]; } else tree = array[top]; }//end of if } };