Указатель неожиданно изменяется

Question

Я кодирую красно-черное дерево, следуя Введение в алгоритмы. И когда дело касается функции правого поворота, один из моих указателей был неожиданно изменен.

void RBTree::RightRotate(pNode &z) 
{ 
    pNode l=z->lChild; 
    z->lChild = l->rChild;  //link z->l-r to z as a lChild 
    if(l->rChild != nil)   
     l->rChild->p = z;  
    l->p = z->p;    //when pass the tree's root as parameter 
           //z,after executing this line, z was 
           //modified to pointing to nil 
           //(known from debug window), why? 
    if(z->p == nil)    
     root = l; 
    else if (z == z->p->lChild) 
     z->p->lChild = l; 
    else 
     z->p->rChild = l; 
    l->rChild=z; 
    z->p=l; 
} 

И точно так же, как Введение в алгоритмы идет, я поставил nil указатель в моем классе. Так как только когда корень был передан как параметр z, это может привести к этой проблеме, я откладываю что-то не так с nil и root. Ниже приводится весь код. :

    #include 
    #include 
    #include  
    #define RED 1 
    #define BLACK 0 
    using namespace std; 
    typedef struct Node 
    { 
     int color, val; 
     struct Node* lChild, *rChild, *p; 
     Node(int val_, struct Node* tmp) 
       {color=RED, val=val_,lChild=rChild=p=tmp;} 
     Node(){color=BLACK, val=0,lChild=rChild=p=NULL;} 
    }Node,*pNode; 

    class RBTree 
    { 
    public: 
     RBTree() 
     { 
      root=NULL; 
     } 
     ~RBTree() 
     { 
      Free_(root); 
     } 
     void Free_(pNode p) 
     { 
      if(p!=NULL) 
      { 
       Free_(p->lChild); 
       Free_(p->rChild); 
       delete(p); 
       p=NULL; 
      } 
     } 
     pNode FindMin() const 
     { 
      pNode p=root; 
      if (p) 
       while(p->lChild) 
        p=p->lChild; 
      return p; 
     } 
     pNode FindMax() const 
     { 
      pNode p=root; 
      if (p) 
       while(p->rChild) 
        p=p->rChild; 
      return p; 
     } 
     void Print(pNode p, int n) const 
     { 
      if(!p) 
       return; 
      Print(p->rChild,n+2); 
      for(int i=0;ivalcolor==1)?"R":"B")lChild,n+2); 
     } 
     pNode Root() {return root;} 
     void Insert(int const& val_); 
     void InsertFixup(pNode &z); 
     void LeftRotate(pNode &p); 
     void RightRotate(pNode &p); 
     pNode Search(pNode const &p, int x) const; 
     void Delete(pNode &p, int x); 

    private: 
     pNode root; 
     static pNode nil; 
    }; 

    pNode RBTree::nil = new Node(); 

    /* 
    Inserting pipiline: 
    Insert node into RBTree, then fixup. 
    In the fixup procedure , rotate may be called 
    */ 

    void RBTree::InsertFixup(pNode &z) 
    { 
     while (z->p->color == RED) 
     { 
      pNode y; 
      if (z->p == z->p->p->lChild) 
      { 
       y=z->p->p->rChild; 
       if(y->color == RED) 
       { 
        z->p->color = BLACK; 
        y->color = BLACK; 
        z->p->p->color = RED; 
        z = z->p->p; 
       } 
       else 
       { 
        if(z==z->p->rChild) 
        { 
         z = z->p; 
         LeftRotate(z); 
        } 
        z->p->color = BLACK; 
        z->p->p->color = RED; 
        RightRotate(z->p->p); 
       } 
      } 
      else 
      { 
       y=z->p->p->lChild; 
       if(y->color == RED) 
       { 
        z->p->color = BLACK; 
        y->color = BLACK; 
        z->p->p->color = RED; 
        z=z->p->p; 
       } 
       else 
       { 
        if(z==z->p->lChild) 
        { 
         z = z->p; 
         RightRotate(z); 
        } 
        z->p->color = BLACK; 
        z->p->p->color = RED; 
        LeftRotate(z->p->p); 
       } 
      } 
     } 
     root->color = BLACK; 
    } 
    void RBTree::Insert(int const &val_) 
    { 
     pNode z=new Node(val_, nil);   //set val, lChild, rChild, p to NULL, color to RED 
     pNode x = root; 
     pNode pre = nil; 
     if(NULL == root) 
      root = z; 
     else 
     { 
      while (x!=nil) 
      { 
       pre=x; 
       x=(x->valrChild:x->lChild; 
      } 
      z->p = pre; 
      if (z->val val) 
       pre->lChild = z; 
      else 
       pre->rChild = z; 
     } 
     InsertFixup(z); 
    } 

    //left-rotate 
    //denote z, z's rChild == r 
    //parent changed: z, r, r's lChild 
    //child chagend: z->rChild, r->lChild, z->p->lChild/rChild 
    void RBTree::LeftRotate(pNode &z) 
    { 
     pNode r=z->rChild; 
     z->rChild = r->lChild;  //link p->r-l to p as a r 
     if(r->lChild != nil) 
      r->lChild->p = z; 
     r->p = z->p; 
     if(z->p == nil) 
      root = r; 
     else if (z == z->p->lChild) 
      z->p->lChild = r; 
     else 
      z->p->rChild = r; 

     r->lChild=z; 
     z->p=r; 
    } 
    // right-rotate 
    void RBTree::RightRotate(pNode &z) 
    { 
     pNode l=z->lChild; 
     z->lChild = l->rChild;  //link p->l-r to p as a l 
     if(l->rChild != nil) 
      l->rChild->p = z; 
     l->p = z->p; 
     if(z->p == nil)    //link parent from top to bottom 
      root = l; 
     else if (z == z->p->lChild) 
      z->p->lChild = l; 
     else 
      z->p->rChild = l; 
     l->rChild=z; 
     z->p=l; 
    } 
    int main() 
    { 
     int a[9] = {11, 2, 14, 1, 7, 15, 5, 8, 4}; 
     RBTree tr; 
     for(int i=0;i

я использую ноль в неправильном направлении? Спасибо.

Answer 1

Nill не является выражением C++. Однако некоторые среды могут включать его, просто используя его как псевдоним для NULL или 0. Если вы используете C++ 11, я бы порекомендовал nullptr

Попробуйте взглянуть ли

l->p < z & & z < l->p + sizeof(z)

Если это так, то вы назначаете z.