AA tree class help

This is a discussion on AA tree class help within the C++ Programming forums, part of the General Programming Boards category; My aa tree class has a segment memory fault after the second insertion into the class. Recursion would of been ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121

    AA tree class help

    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

    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
        }
    
    
    };
    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.

  2. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    531
    Nice approach - I like your way of going back up the tree using an array.

    So, a segfault could happen in each split or skew. Consider skew() if adding elements with priority 3 then 4. 3 is the root node, nothing interesting there. What about 4? Since 4 > 3, it'll be inserted to the right.

    Skew is called on the root node, 3.
    Code:
        void skew(AANODE<data> *& Branch)
        {
            if( Branch->left->level== Branch->level && Branch->level   != 0 )
            {
    What is Branch->left? It's NULL, yes? So branch->left->level dereferences a NULL pointer and segfaults.

    If you added the elements the other way around, skew would be fine and split would segfault (because Branch->right->right can't possibly be non NULL when you've only added two elements).

    Think about what you're testing for.... you're looking for links with the same level. So if the link is NULL, it can't be the same level. So, you should check that Branch, Branch->left etc are not NULL before trying to examine the levels.


    You have a couple of coding errors, but nothing major:

    You're decrementing "top" twice in the while loop -- once at the beginning and once at the end. I think you just want to do it once.

    Your rotation code for split is slightly wrong -- probably just a transcription-from-pseudocode error -- you should check it.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    I was able to spot problems by comparing it directly with my own AA-Tree implementation.

    In this line of code the check for Branch->level being non-zero occurs after Branch->left->level is examined.
    Code:
    if( Branch->left->level== Branch->level && Branch->level   != 0 )
    In my code for the same line I do the equivalent of:
    Code:
    if (Branch->left != NULL && Branch->level == Branch->left->level)
    Notice the NULL check? This is instead of checking for zero on the level. You can tell from my line of code that the NULL check occurs before using Branch->left and that if it did not that it would crash. You likewise need to switch around the order of your short-circuit evaluation.

    Note that it's actually safer to check the pointer for NULL instead of checking the level for zero. That's because if there were some bug that updated the level incorrectly then it would crash whereas checking for NULL would not.

    Split has the same problem, although there you need to check two things for NULL.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121
    Thank you for the help!

    I did ran into a new error with a new modified version of my AAtree. My search function goes into segment fault! I believe a pointer is lost somewhere ~_~


    Code:
     template <class data>
    struct AANODE
    {
        unsigned int level;
        unsigned int key;
        data * hold;
        AANODE<data> * left;
        AANODE<data> * right;
    };
    
    
    template <class data>
    class AATREE
    {
    
        AANODE<data> * tree;
    
           inline void skew(AANODE<data> * & node)
        {
          if(node->left != 0 && node->level == node->left->level )
          {
            AANODE<data> *  tempt = node->left;
            node->left = tempt->right;
            tempt->right = node;
            node = tempt;
          }
        }
    
        inline void split(AANODE<data> * & node)
        {
            if( (node->right != 0 && node->right->right != 0 ) && node->level == node->right->right->level)
            {
            AANODE<data> *  tempt = node->right;
            node->right = tempt->left;
            tempt->left = node;
            node = tempt;
            ++node->level;
            }
        }
    
        public:
    
        AATREE(void){ tree = 0; }
    
        void insert( data * item, unsigned int Key )
        {
           if( tree == 0)
           {
            tree = new AANODE<data>;
            tree->hold = item;
            tree->left = tree->right = 0;
            tree->level = 1;
            tree->key = Key;
           }
           else
           {
              AANODE<data> * ptr = tree;
              std::vector< AANODE<data> *> array;
              unsigned int top = 0;
              while(1)
              {
                ++top;
                array.push_back(ptr);
                if( Key <  ptr->key )
                if( ptr->left == 0 )
                {break;}
                else
                {ptr = ptr->left;}
    
                if( Key >  ptr->key )
                if( ptr->right == 0 )
                {break;}
                else
                {ptr = ptr->right;}
    
              }
    
              if( Key <  array[top]->key )
              if( array[top]->left == 0  )
              {
                  array[top]->left = new AANODE<data>;
                  array[top]->left->key = Key;
                  array[top]->left->left = ptr->left->right = 0;
                  array[top]->left->hold = item;
                  array[top]->left->level = 1;
              }
    
              if( Key >  array[top]->key )
              if( array[top]->right == 0  )
              {
                  array[top]->right = new AANODE<data>;
                  array[top]->right->key = Key;
                  array[top]->right->left = ptr->right->right = 0;
                  array[top]->right->hold = item;
                  array[top]->right->level = 1;
              }
    
    
            for( ; --top != 0; )
            {
                skew(array[top]);
                split(array[top]);
    
    
                if(array[top - 1]->left == array[top])
                array[top - 1]->left = array[top];
    
                if(array[top - 1]->right == array[top])
                array[top-1]->right == array[top];
            }
            tree = array[top];
           }//end of else
    
        }
    
        data * search(unsigned int Key)
        {
            AANODE<data> * ptr = tree;
            while(ptr != 0)
            {
                if( ptr->key == Key)
                return ptr->hold;
    
                if(Key < ptr->key )
                ptr = ptr->left;
    
                if(Key > ptr->key)
                ptr = ptr->right;
            }
    
            return 0;
        }
    
    
    };

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    This can really only mean one thing, that your tree was corrupt at the point you called search.

    I suggest using tree Verify function. This function can be called before and after each operation to confirm that the function does not screw up the tree. check as many conditions as you can.
    Here's what my one looks like:
    Code:
    template <class TNode>
    bool Verify(const TNode *head, const int &headlevel) {
    	if (head != NULL) {
    		if (head->left != NULL) {
    			if ((*head < *(head->left))
    			|| (head->right == NULL)
    			|| (head->level == head->left->level)
    			|| !Verify(head->left, head->level)) return false;
    		}
    		if (head->right != NULL) {
    			if ((*(head->right) < *head)
    			|| (headlevel == head->level && head->level == head->right->level)
    			|| !Verify(head->right, head->level)) return false;
    		}
    	}
    	return true;
    }	
    
    template <class TNode>
    bool Verify(const TNode *head) {
    	int headlevel = -1;
    	return Verify(head, headlevel);
    }
    I call Verify and if the tree is in okay then it returns true. If the tree is corrupt in almost any way then it returns false.
    Hope that helps.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121
    I realize one error thankfully!!

    Code:
    bool direction;
            for( ; --top > 0; )
            {
                if(array[top - 1]->right == array[top])
                direction = true; //right
                else
                direction = false;//left
    
                skew(array[top]);
                split(array[top]);
    
    
                if( direction == false)
                array[top - 1]->left = array[top];
    
                if( direction == true )
                array[top - 1]->right = array[top];
            }
            tree = array[top];
    prior to spew and split the node, The tree needed the correction direction of placing the node.
    Though, I thank you for the verify function! I'm still figuring out how the tree is losing a node.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    Lol "spew"

    Sorry I just dumped the code before, I was out of time. It requires the definition of a less-than operator to work, or alternatively in your case you can change the less-than comparisons to comparing the key directly.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 08-11-2008, 04:19 AM
  2. A simple Tree class problem.
    By msp in forum C++ Programming
    Replies: 4
    Last Post: 08-19-2007, 10:52 PM
  3. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  4. can't insert data into my B-Tree class structure
    By daluu in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2002, 05:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21