AA tree class help

**Darkinyuasha1** · 01-06-2012

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.

**smokeyangel** · 01-06-2012

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.

**iMalc** · 01-06-2012

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.

**Darkinyuasha1** · 01-13-2012

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


};

**iMalc** · 01-14-2012

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.

**Darkinyuasha1** · 01-14-2012

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.

**iMalc** · 01-14-2012

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.

Thread: AA tree class help

Thread Tools

Search Thread

Display

AA tree class help

Similar Threads

trying to use a static Binary search tree with another CLASS

A simple Tree class problem.

can anyone teach me how to convert a general tree to binary tree and vice versa?

can't insert data into my B-Tree class structure