title: Runtime Error in spoj (SBANK) - using red-black tree
body: <p>I am trying to solve SBANK problem in spoj (<a href="http://www.spoj.com/problems/SBANK/" rel="nofollow">http://www.spoj.com/problems/SBANK/</a>) using a red-black tree. When i try to submit the solution, i keep getting a RUNTIME (SIGSEGV) error. </p>
  
  <p>Also, i am not able to use this implementation (code given below) of a red-black tree in any online judge (keep getting the same error). I have tried debugging the code but couldn't find the source of it.</p>
  
  <p>Can anyone please help me debug it?</p>
  
  <pre><code>#include&lt;bits/stdc++.h&gt;
  using namespace std;
  
  struct node
  {
      string key;
      int rep;
      char color;
      struct node *parent,*llink, *rlink;
  };
  
  
  class rbtree
  {
      struct node *root;
  
      public:
  
          rbtree()
          {
              root = NULL;
          }
  
          void left_rotate(node *nn)
          {
              struct node *temp = nn-&gt;rlink;
              nn-&gt;rlink = temp-&gt;llink;
              if(temp-&gt;llink != NULL)
                  temp-&gt;llink-&gt;parent = nn;
  
              temp-&gt;parent = nn-&gt;parent;
  
              if(temp-&gt;parent == NULL)
                  root = temp;
              else if(nn == nn-&gt;parent-&gt;llink)
                  nn-&gt;parent-&gt;llink = temp;
              else
                  nn-&gt;parent-&gt;rlink = temp;
  
              temp-&gt;llink = nn;
              nn-&gt;parent = temp;
              temp = NULL;
              delete temp;
          }
  
  
          void right_rotate(node *nn)
          {
              struct node *temp = nn-&gt;llink;
              nn-&gt;llink = temp-&gt;rlink;
              if(temp-&gt;rlink != NULL)
                  temp-&gt;rlink-&gt;parent = nn;
              temp-&gt;parent = nn-&gt;parent;
              if(temp-&gt;parent == NULL)
                  root = temp;
              else if(nn = nn-&gt;parent-&gt;llink)
                  temp = nn-&gt;parent-&gt;llink;
              else
                  temp = nn-&gt;parent-&gt;rlink;
              temp-&gt;rlink = nn;
              nn-&gt;parent = temp;
              temp = NULL;
              delete temp;
          }
  
  
          void insert_fixup(struct node *nn)
          {
              while(nn != root &amp;&amp; nn-&gt;parent-&gt;color == 'r')
              {
                  struct node *uncle;
                  if(nn-&gt;parent == root)
                      uncle = NULL;
                  else if(nn-&gt;parent == nn-&gt;parent-&gt;parent-&gt;llink)
                      uncle = nn-&gt;parent-&gt;parent-&gt;rlink;
                  else
                      uncle = nn-&gt;parent-&gt;parent-&gt;llink;
  
                  if(uncle != NULL &amp;&amp; uncle-&gt;color == 'r')
                  {
                      nn-&gt;parent-&gt;color = 'b';
                      uncle-&gt;color = 'b';
                      nn-&gt;parent-&gt;parent-&gt;color = 'r';
                      nn = nn-&gt;parent-&gt;parent;
                  }
                  else
                  {
                      if(nn-&gt;parent == nn-&gt;parent-&gt;parent-&gt;llink)
                      {
                          if(nn == nn-&gt;parent-&gt;llink)
                          {
                              char ch = nn-&gt;parent-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;parent-&gt;color = nn-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;color = ch;
                              right_rotate(nn-&gt;parent-&gt;parent);
                          }
                          else
                          {
                              char ch = nn-&gt;parent-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;parent-&gt;color = nn-&gt;color;
                              nn-&gt;color = ch;
                              left_rotate(nn-&gt;parent);
                              right_rotate(nn-&gt;parent-&gt;parent);
                          }
                      }
                      else
                      {
                          if(nn == nn-&gt;parent-&gt;rlink)
                          {
                              char ch = nn-&gt;parent-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;parent-&gt;color = nn-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;color = ch;
                              left_rotate(nn-&gt;parent-&gt;parent);
                          }
                          else
                          {
                              char ch = nn-&gt;parent-&gt;parent-&gt;color;
                              nn-&gt;parent-&gt;parent-&gt;color = nn-&gt;color;
                              nn-&gt;color = ch;
                              right_rotate(nn-&gt;parent);
                              left_rotate(nn-&gt;parent-&gt;parent);
                          }
                      }
                  }
              }
              root-&gt;color = 'b';
          }
  
          void insert(string key)
          {
              struct node *cur,*parent,*newnode;
              newnode = new node;
              newnode-&gt;key = key;
              newnode-&gt;rep = 1;
              newnode-&gt;color = 'r';
              newnode-&gt;llink = NULL;
              newnode-&gt;rlink = NULL;
              newnode-&gt;parent = NULL;
  
              if(root == NULL)
                  root = newnode;
              else
              {
                  cur = root;
                  while(cur != NULL)
                  {
                      parent = cur;
                      if(cur-&gt;key == key)
                      {
                          cur-&gt;rep++;
                          return;
                      }
                      else if(cur-&gt;key &gt; key)
                          cur = cur-&gt;llink;
                      else
                          cur = cur-&gt;rlink;
                  }
                  if(parent-&gt;key &gt; key)
                  {
                      parent-&gt;llink = newnode;
                      newnode-&gt;parent = parent;
                  }
                  else
                  {
                      parent-&gt;rlink = newnode;
                      newnode-&gt;parent = parent;
                  }
              }
              insert_fixup(newnode);
              newnode = NULL;
              delete newnode;
          }
  
          void print()
          {
              inorder(root);
          }
  
          void inorder(node *nn)
          {
              if(nn != NULL)
              {
                  inorder(nn-&gt;llink);
                  cout&lt;&lt;nn-&gt;key&lt;&lt;" "&lt;&lt;nn-&gt;rep&lt;&lt;endl;
                  inorder(nn-&gt;rlink);
              }
              nn = NULL;
              delete nn;
          }
  
          void destroy(node *nn)
          {
              if(nn != NULL)
              {
                  destroy(nn-&gt;llink);
                  destroy(nn-&gt;rlink);
                  if( nn != root)
                      delete nn; 
              }
          }
  
          void del()
          {
              destroy(root);
              delete root;
          }
  };
  
  int main()
  {
      int t;
      scanf("%d",&amp;t);
      int n;
      string s;
      char c;
      while(t--)
      {
          rbtree tree;
          scanf("%d",&amp;n);
          scanf("%c",&amp;c);
          while(n--)
          {
              getline(cin,s);
              s.erase(s.end()-1);
              tree.insert(s);
          }
          tree.print();
          tree.del();
          printf("\n");
      }
      return 0;
  }
  </code></pre>