Implementation of Red black tree in C++ using global pointer

Question

I am having trouble updating my global pointer in the following code,

#include <iostream>

using namespace std;

struct RB{
    RB()=default;
    RB(int clr):color(clr) { }
    int color;
    RB *p,*left,*right;
    int key;
};

RB *Tnil=new RB(0);
RB *T=Tnil;
void insert(RB *T,RB *z)
{
    RB *y=Tnil;
    RB *x=T;
    while(x!=Tnil)
    {
        y=x;
        if(z->key<y->key)
          x=x->left;
        else
         x=x->right;
    }
    z->p=y;
    if(y==Tnil)
      T=z;
    else if(z->key<y->key)
      y->left==z;
    else
      y->right=z;
    z->right=Tnil;
    z->left=Tnil;
    z->color=1;
}

void print(RB *T)
{
    if(T==Tnil)
      return;
    print(T->left);
    cout<<T->key;
    print(T->right);
}

int main()
{
  for(int i=1;i<10;++i)
  {
    RB *x=new RB;
    x->key=i;
    insert(T,x);

  }
   print(T);
}

The problem is, the comparison y==Tnil in my insert function evaluates to false when I expected it to be true. After ending the function, T again becomes equal Tnil, as a result, so nothing gets inserted. Any help?

Answer 1

Your naming is messed up.

You have two variables named T, one at global scope and the other as parameter to insert. Therefore the assignment T=z; in insert does not actually work on the global variable T but on the parameter and hence has no side-effect outside the function.

As a general rule, try to avoid single-letter variable names like T, z and x. They make your code hard to read and can easily hide mistakes like this one. Also, avoid doing non-localized updates from within functions. Updating global variables from functions is just asking for trouble like this. A better approach would be to have insert return a pointer to the new top-level node instead.

Answer 2

you want to update global T.
Therefore you should pass a reference of global T to insert:

replace

void insert(RB *T,RB *z)

with

void insert(RB * & T,RB *z)

(otherwise just a copy of global pointer T gets updated)

Also as mentioned by ComicSansMS in your example

y->left==z 

should be replaced by

y->left=z

Best,

Jack