• 11-03-2010
ychen42
hi all!

so i have an assignment for red black tree

i have to implement 2 functions and inside these function my prof said i need to inline implement 1 other function inside each

im having trouble with this(well actually im clueless)

can someone teach me where to insert the inline functions needed and also give me the correct declaration of it

i have done inline functions before but they were like this:
but ive never done an inline that required many steps

heres my code

Code:

```bool Tree::insert(val_type x)       {       //PROBLEM FOR THE STUDENT               treeNode* z = new treeNode; // create new node for insert         z->data = x; // set insert data to z               treeNode* y = NULL;         treeNode* r = root;               while(r != NULL)         {         // loop will go try to find a leaf to place the new node         // if node is in tree already no insert is done                     y = r;                     if(z->data == y->data)               return true;             else if(z->data < y->data)               r = r->left;             else               r = r->right;         }               z->parent = y;               if(y == NULL)             root = z;         else             if(z->data < y->data)               y->left = z;             else               y->right = z;               // now z node is a leaf and we set its "children" to nil         z->left = NULL;         z->right = NULL;         // z is the new node inserted so it will be colored red         z->red = true;               return true;       }```
^ in this one i have to add the inline insertfixup() in here somewhere in here but i dont know where or how

Code:

```void Tree::remove(csc212::val_type x)       {       //PROBLEM FOR THE STUDENT             treeNode* y;           treeNode* z = search(x);           treeNode* w;           if(z->left == NULL || z->right == NULL)                   y = z;           else                   y = treeSuccessor(z);           if(y->left != NULL)                   w = y->left;           else                   w = y->right;           w->parent = y->parent;           if(y->parent == NULL)                   root = x;           else if(y == y->parent->left)                   y->parent->left = x;           else                   y->parent->right = x;           if(y != z)                   z->data = y->data;           if(y->red == false)                   deleteFixup(w);           }```
^ same thing im suppose to implement the treeSuccessor() but i dont know how

• 11-03-2010
laserlight
An inline function is either a function declared as inline with the inline keyword, or a member function declared in the class definition. I suspect that your instructor just wants you to do the latter.
• 11-03-2010
ychen42
ya thats how i remembered inline

we declare the function in the header file

but my prof wants me to insert this inline function inside (lets say) the insert function
is that even doable??? maybe im misunderstanding him
• 11-03-2010
laserlight
Quote:

Originally Posted by ychen42
but my prof wants me to insert this inline function inside (lets say) the insert function
is that even doable??? maybe im misunderstanding him

That is not possible in standard C++. In the next version of C++, something like that will be possible, but not now, except where simulated with a library, but that is not what your prof is likely to ask about.
• 11-03-2010
ychen42
thats what i thought lols

so would this sound better:

void someFunction(){

blah blah blah

inline anotherFunction(){

some stuff

}
}

^which generates all kinds of errors
should i just try to implement anotherFunction() inside of someFunction without declaring it as inline ie

void someFunction(){

blah blah blah

"somestuff" // implemented anotherFunction but in different that will fit into anotherFunction

}

^if that made sense at all

ive already implemented insertFixup() and treeSuccessor() can you check them out and help understand how i can insert them into functions without actually using inline?
• 11-03-2010
ychen42
Quote:

Sorry about that- there was a similar "problem" with deletefixup that was mentioned earlier. When I wrote mine, I did everything inline, so there was no need for the auxiliary functions insertfixup and deletefixup. For now, try to write it inline (i.e., keep everything inside of the insert function for the tree). This should work out okay (I'm living proof). Sorry for having to constrain the interface, but if I didn't, I would spend all of my time grading...
• 11-03-2010
laserlight
Oh, then your prof is not talking about inline functions. He is talking about writing the code that might be placed into another function, in the same place as the rest of the code. You might say that you are manually inlining the function :)
• 11-03-2010
ychen42
damn...

that seems harder...

well at least now one thing is cleared up lols

thx for the help miss :)
• 11-03-2010
ychen42
can u help me somehow transcribe these codes into my methods???

i tried doing it n its not working somehow my program went from 5 errors to 101 -.-!

Code:

```treeNode* treeSuccessor(treeNode* x){ if(x->right != NULL)     return treeMinimum(x->right); treeNode* y; y = x->parent; while(y != NULL) { if(x == y->right) { x = y; y = y->parent; } return y; }```
^ this is to be inserted into the remove()

Code:

```void insertFixup(treeNode* z) { treeNode* y; while(z->parent->red == true) { if(z->parent == z->parent->parent->left) { y = z->parent->parent->right; if(y->red == true) { z->parent->red = false; y->red = false; z->parent->parent->red = true; z = z->parent->parent; } else { if(z == z->parent->right) { z = z->parent; rotateLeft(z); } z->parent->red = false; z->parent->parent->red = true; rotateRight(z->parent->parent); } } else { z = z->parent; rotateRight(z); } z->parent->red = false; z->parent->parent->red = true; rotateLeft(z->parent->parent); } root->red = false; }```
^this is the insert fix up