hi, i'm a relatively new Perl programmer -- i normally code in either C,C++ or Java. i'm working as an intern this summmer, and working on a red-black binary tree implementation problem. i'm pretty sure it's a Perl syntax problem. Not blessed w/ vast knowledge about the language, it would be great if i could get some help!

here's the situation:

after i delete a node, and modify the necessary parent/child pointers, my tree becomes corrupted, and several nodes near the region where a node was deleted as a result of the delete function call lose their parent pointers.

at the end of my delete function (displayed below) i return my "successor" node (the smallest node larger than the node being deleted). if the deleted node doesn't have a left or right child, this "successor" node is the node itself. in this situation, once i exit the delete function, i lose information about the parent pointers for the nodes to the left or right of the deleted node (which are moved up, and become the children of the deleted node's parent). instead, their parent pointers are set to undefined.

here's the interesting part: at the end of my delete function, i return the successor node (referred to as $curr). if i have a receiver for the returned $curr node outside of my program, everything works fine. it's just that when there is no receiver (hence $curr is garbage collected) that the tree becomes corrupted. this is strange, because the new pointers set after the node is deleted don't intersect with the returned node.

any hints on how to fix this? both my mentor and i are officially stumped. thanks!

- frustrated_intern

code shown below: 

sub RBDelete{  

  
    my($self, $key) = @_;
    
    if($self->isEmpty){ #empty tree
        die "Illegal Operation 4: Cannot delete without first insertin
+g.";
    }

    my $node = $self->RBSearch($key); #find node in tree 

    if(!(defined $node)){ #non-inserted node
        die "Illegal Operation 5: Cannot delete node without first ins
+erting it.";
    }

    if($node->equals($self->{_root}) == 1) && $node->isLeaf){
        $self->{_root} = ref($node); 
        return;
    }
    
    my $curr;
    my $temp;
    
    if(!($node->hasLeft) || !($node->hasRight)){
        $curr = $node;
    }else{
     
        $curr = $node->mySuccessor;  #successor node -- 
    }
  

    if($curr->hasLeft){
        $temp = $curr->getLeft;
    }elsif($curr->hasRight){
        $temp = $curr->getRight;
    }else{
        $temp = $self->{_sentinel_node}; #set up sentinel node as "dum
+my node"
       
    }
    
    my $currP = $curr->getParent; 
    
    if($node->isRoot){
        $self->{_root}->markRoot(0);
        $self->{_root} = $temp; 
        $temp->markRoot(1);
    
    }elsif($curr->equals($curr->getParent->getLeft)){ #curr is left ch
+ild 
        if(defined $temp->getNodeKey){ #set temp to cur's parent  
           $currP->setLeft($temp);
            
        }else{
           
            $currP->removeLeft;
        }
        
    }else{
        if(defined $temp->getNodeKey){  #curr is right child 
            $currP->mySetRight($temp);  #set temp as curr's parent's r
+ight child
          
        }else{
            $currP->removeRight;
        }
    }

    my $currColor = $curr->getNodeColor; 
    if($curr->equals($node) == 0){ #curr and node distinct nodes -- sh
+ift curr up to node's position
        my $nodeRight = $node->getRight; 
        my $nodeLeft = $node->getLeft;
        
        $node->{_right} = undef;
        $node->{_left} = undef; 
        if($node->isRoot){
            $self->{_root}->markRoot(0);
            $curr->markRoot(1);
            $self->{_root} = $curr; 
        }else{
            if($node->equals($node->getParent->getLeft)){
                $node->getParent->setLeft($curr);
            }else{
                $node->getParent->setRight($curr);
            }
        
        }

        if(defined $nodeRight){
            $curr->setRight($nodeRight); 
        }

        if(defined $nodeLeft){
            $curr->setLeft($nodeLeft);
        }
        
        $curr->setNodeColor($node->getNodeColor);
            
    }

    if($currColor == 0){
        $self->RBDeleteFix($temp);
    }
    return $curr;
    
}

[download]

Edit g0n: closed b tag after "here's the situation"

In reply to help! red-black binary tree problem by frustrated_intern

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.