i have included just insert function in redblacktree class.
there are no compilation errors but it shows segmentation fault on running.
when i am calling insert function it's not even entering into it as it's not printing the cout statement at first line of insert body.
i am using g++ compiler in linux ubuntu.
i am wondering what is wrong.

#include<iostream>
using namespace std;

template <class T>
class redblacktree {
private:
T x;
redblacktree<T> *left, *right, *parent;
int leftsize; // number of nodes in left subtree
int r; // the number of black nodes on any path
// from the current node to a leaf in its subtree
bool color;
redblacktree<T> *root;
public:

redblacktree():root(NULL){}
void insert(T y)
{
 cout<<"root->x=";
 redblacktree<T> *p,*q;
 if(root==NULL)
 {
  p=new redblacktree<T>;
  p->x=y;
  p->left=p->right=p->parent=NULL;
  p->leftsize=0;
  p->r=1;
  p->color=false;
 cout<<"root->x="<<root->x;
 }

 else
 {
  while(p!=NULL)
  {
   p=root;
   if(y>p->x)
    p=p->right;
   else if(y<p->x)
    p=p->left;
  }
  q=new redblacktree<T>;
  q->x=y;
  q->left=p->right=NULL;
  q->parent=p;
  q->leftsize=0;
  q->r=0;
  q->color=true;
  while((q->parent->left==q)&&(q->parent!=NULL))
  {
   q=q->parent;
   q->leftsize+=1;
  }
 }
}
};

int main()
{
redblacktree<int> rb;
rb.insert(1);

}

when i am calling insert function it's not even entering into it as it's not printing the cout statement at first line of insert body.

It does enter that function. The buffer does not flush straight away. If you add an endl to the end of line 19, you'll see the output.

Time for you to learn how to use the debugger. Here is the relevant part of the debug process showing how I found your error:


Program received signal SIGSEGV, Segmentation fault.
0x0804871f in redblacktree<int>::insert (this=0xbffff360, y=1) at 28.cpp:29
29 cout<<"root->x="<<root->x;
(gdb) print root
$1 = (redblacktree<int> *) 0x0


So, it seems that your pointer root is a null pointer in line 29. Bizarrely, you already know this, because your code only enters that section if root==NULL. You cannot dereference a NULL pointer. It causes a segmentation fault.

Edited 5 Years Ago by Moschops: n/a

Comments
Perfect introductio to debugging

thanks very much for introducing me to this new concept.
after u told that root is still equal to NULL i realized that i missed one instruction
root=p;
thank u very much for pointing out the mistake.

hey, 1 thing i wanted to ask is which debugger u used and can u provide me link to the stuff how to debug the program using debugger.

This question has already been answered. Start a new discussion instead.