Hey ya'll! My friends and I are new to this so please be gentle. We have the following code and we know the problem lies with the insert function. We need some helpful insights or fixes. Thank You!

//This is the header bst.h:

#include <cstdlib>
#include <iostream>
using namespace std;

struct vertex
{
int key;
int color;
//0 is red, 1 is black
vertex *left;
vertex *right;
vertex *p;
};

class btree
{
private:
vertex *root;
void insert( int key, vertex *leaf );
void fixUp( vertex *z );
void rightRotate( vertex *z );
void leftRotate( vertex *z );
vertex *search( int key, vertex *leaf );
//void postorderPrint( vertex *leaf );
void destroy_tree( vertex *leaf );
void postorderPrint( vertex *leaf );
public:
btree();
~btree();
vertex *getRoot(){ return root; };
void insert( int key );
vertex *search( int key );
void postorderPrint();
void destroy_tree();
};
btree::btree(){ root = NULL; }
btree::~btree(){}
destroy_tree();
void btree::insert( int key, vertex *leaf )
{
if( key < leaf->key )
{
if( leaf->left != NULL )
{
insert( key, leaf->left );
}
else
{
leaf->left = new vertex;
leaf->left->key = key;
leaf->left->color = 0;
leaf->left->p = leaf;
leaf->left->left = NULL;
//sets the left child of the child vertex to null
leaf->left->right = NULL;
//sets the right child of the child vertex to null
fixUp( leaf->left );
}
}
else if( key >= leaf->key )
{
if( leaf->right != NULL )
{
insert( key, leaf->right );
}
else
{
leaf->right = new vertex;
leaf->right->key = key;
leaf->right->color = 0;
leaf->right->p = leaf;
leaf->right->left = NULL;
//sets the left child of the child vertex to null
leaf->right->right = NULL;
//sets the right child of the child vertex to null
fixUp( leaf->right );
}
}
}

void btree::insert( int key )
{
if( root != NULL )
{
insert( key, root );
}
else
{
root = new vertex;
root->key = key;
root->color = 0;
root->p = NULL;
root->left = NULL;
root->right = NULL;
}
}
void btree::fixUp( vertex *z )
{
while( z!= root && z->p->color == 0 )
{
if( z->p == z->p->p->left )
{
if( z->p->p->right->color == 0 )
{
z->p->color = 1;
z->p->p->right->color = 1;
z->p->p->color = 0;
z = z->p->p;
}
else if( z == z->p->right )
{
z = z->p;
leftRotate( z );
}
z->p->color = 1;
z->p->p->color = 0;
rightRotate( z );
}
else( z->p == z->p->p->right )
{
if( z->p->p->left->color == 0 )
{
z->p->color = 1;
z->p->p->left->color = 1;
z->p->p->color = 0;
z = z->p->p;
}
else if( z == z->p->left )
{
z = z->p;
rightRotate( z );
}
z->p->color = 1;
z->p->p->color = 0;
leftRotate( z );
}
}
root->color = 1;
}
void btree::leftRotate( vertex *x )
{
x->right = x->right->left;
if( x->right->left != NULL )
{
x->right->left->p = x;
}
x->right->p = x->p;
if( x->p == NULL )
{
root = x->right;
}
else if( x = x->p->left )
{
x->p->left = x->right;
}
else
{
x->p->right = x->right;
}
x->right->left = x;
x->p = x->right;
}
void btree::rightRotate( vertex *y )
{
y->left = y->left->right;
if( y->left->right != NULL )
{
y->left->right->p = y;
}
y->left->p = y->p;
if( y->p == NULL )
{
root = y->left;
}
if( y->p->left == y )
{
y->p->left = y->left;
}
else
{
y->p->right = y->left;
}
y->left->right = y;
y->p = y->left;
}
vertex *btree::search( int key, vertex *leaf )
{
if( leaf != NULL )
{
if( key == leaf->key )
{
return leaf;
}
if( key < leaf->key )
{
return search(key, leaf->left);
}
else
{
return search( key, leaf->right );
}

}
else
{
return NULL;
}
}
vertex *btree::search( int key )
{
return search( key, root );
}
void btree:ostorderPrint( vertex *leaf )
{
if( leaf != NULL )
{
postorderPrint( leaf->left );
print items in left subtree.
postorderPrint( leaf->right );
print items in right subtree.
cout << leaf->key << " ";
print the root item.
}

}
void btree:ostorderPrint()
{
postorderPrint( root );
}
void btree::destroy_tree( vertex *leaf )
{
if( leaf != NULL )
{
destroy_tree( leaf->left );
destroy_tree( leaf->right );
delete leaf;
}
}

void btree::destroy_tree()
{
destroy_tree( root );
}

//This is the bst.cpp:


#include "bst.h"
#include "time.h"

int main()

{
time_t seconds;
time( &seconds );


srand( (unsigned int) seconds );


btree bst;

int l = 1 + rand() % 1000;


for( int i = 0; i < 100; i++ )
{
while( bst.search( l ) != NULL )
{
l = 1 + rand() % 1000;

}


bst.insert( l );

}
bst.postorderPrint();

cout << "\n";
return 0;
}

Please edit your post to use [code][/code] tags.

Just glancing, not familiar with C++, but shouldn't be more like

Sorry, but there are lots of problems.

Corrections are needed just to get the code to compile. Also, since you didn't use CODE tags, two spots in the code turned into smileys, creating two more reasons it won't compile.

You had:
I assume you meant
You had
I assume you meant to have // before the comments.

And Proud already mentioned another compile time error.

It is harder to be sure about the many logic errors, because there are enough that the intent of the code is unclear. But an example of a logic error is:
What happens if z-p happens to be the root? Then z->p->p is NULL and z->p->p->left is a seg fault.

A Red/Black tree coded the way you have done take much more code than it should and more code represents more opportunities for errors. That makes the code harder to write, much harder to manually check and harder to effectively test.

The biggest change to improve the code size and readability is to let the side be a variable: Instead of
You should have
Then, instead of (several sections of code similar to):
You can use code similar to
When side is a variable in tree code, you often need to refer to the other side. I like to make that explicit in the code using an inline function:
Notice that left and right were defined such that 1-left==right and 1-right==left.
Then in code where side is a variable, you can use other(side) to refer to the other side.

In your code, you had a comment
But as I looked through other sections of your code it seemed like sometimes you meant the opposite. It's hard to tell whether some parts were wrong Red/Black tree logic applied to your color scheme (0 is red) or were Red/Black tree logic but using the opposite color scheme. To make the intent of the code clearer, use enums.
Then use red and black instead of 0 and 1 for colors in the rest of the code.

In most Red/Black code, you often need to check whether a sibling is red, but you sometimes need to be careful of the case that the sibling doesn't exist. Your tree appears to use NULL, rather than a dummy black node for the layer below all the real nodes. With that design (which I also prefer) it is safest to check for red with an inline function:

Thanks johnsfine! I really appreciate the help. For the logic error you mentioned:

It is harder to be sure about the many logic errors, because there are enough that the intent of the code is unclear. But an example of a logic error is:
Code:

while( z!= root && z->p->color == 0 )
{
if( z->p == z->p->p->left )

What happens if z-p happens to be the root? Then z->p->p is NULL and z->p->p->left is a seg fault.

How would I fix that?

Check the bad condition first with a short-circuit operator so that the expression that would seg-fault isn't evaluated unless it's safe to do so?

ok, just a few notes:

1)
why the condition in the second part? Just curious...

2)
why don't you use a constructor for that?

3)
maybe you meant
4)
you should also check that (z->p != root)

5)
check that z->p->p->right is not NULL;
You access a lot of items and their components without checking that they exit. I fixed about 3 or 4 such things in the code, then I gave up.

6) in btree::rightRotate( vertex *y )
Now I don't really follow this pointer switching chaos, but it seems to me that you will lose y->left with its entire left branch, since you forget all pointers that point to it.

I think the actual error for that point was elsewhere, in the function
When you insert the very first vertex into the tree (as the root) you make it red. That causes the later problem.
The root ought to always be black.
If the root is black, then your loop that detects the parent is red would be OK with its assumption that the parent is not the root.

The next logic error seems to be due to poor attention to where the braces go:
At the point I commented in red, you are done with the current iteration of the loop. You want to do the next iteration of the loop. But as you coded it, you fall through to the second rotation.
The simple, but tacky solution is to use a continue instruction to get back to the loop. The more elegant solution is to arrange all your {}s correctly so nothing more i done in this iteration.
At the point I commented in blue, you are done with the entire loop. I think you might need a beak instruction to cover that case.

I find most of the red/black tree online descriptions confusing for the insertion fixup and really confusing for the deletion fixup. I think my own version the insertion fixup description is clearer. In hopes it might help some of those participating in this thread, here it is:

Variables, all described together here for clarity, but each should not be defined in the flow of code until it is first needed:

N a newly red node (either a new node or one that just became red)
P parent of N
G grandparent of N
S the side of G that does NOT contain P
U uncle of N (child on side S of G)

Top of loop:
1) If N is the root, color it black and break
2) If P is black, break
3) If U is non-null and red, change P and U to black, change G to red. N=G (the newly red node) and goto top of loop.
4) If N is on side S of P then rotate(1-S,P)
5) change G to red, change child[1-S] of G to black, rotate(S,G) and break

That's the whole thing. If you don't allow the side to be a variable, that doubles most of the code representing the "value" of S by which of two mirror image copies of the code you are in.

Notes: after (1) we know N isn't the root so P is not null.
after (2) we know P is red, so it isn't the root (which is always black) so we know G is not null and we even know G is black. But it is still possible that U is null.
At step (5) it is possible that G is the root, so the rotate function needs to cover that possibility.

Since most programmers hate gotos you can construct an appropriate loop to give the same flow of control (which is actually clearer with the goto).

To make rotate save and understandable, you want a couple helper functions inside the vertex class. Here is the version based on side being a variable. If you keep the design with doubled code and side not a variable, then you need a setLeft and setRight function instead of just set (and replace takes more code).

The first helper function sets child s of this to x, and sets the corresponding back pointer, but allows for the possibility that x is NULL.
The second one replaces whichever child of this was x with y.

With those, rotate is easy
Notice the sequence of steps is significant. Each value is overwritten after being used for the last time. The red last use of the prior value of x->ch[1-s] comes before the purple setting the new value of x->ch[1-s]. The blue last use of the prior value of y->ch[s] comes before the green setting the new value of y->ch[s]. The orange last use of the prior value of x->p comes before the yellow setting the new value of x->p.

In your version of rotate, you replaced x->right at the beginning, but then used what needed to be the prior value of x->right throughout. In all your code, I think a few more tmp variables and less -> chains would have added clarity. But if you don't want tmp variables you need better care about the sequence: