sub RBDelete{  

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

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

    if(!(defined $node)){ #non-inserted node
        die "Illegal Operation 5: Cannot delete node without first inserting 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 "dummy 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 child 
        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 right child
          
        }else{
            $currP->removeRight;
        }
    }

    my $currColor = $curr->getNodeColor; 
    if($curr->equals($node) == 0){ #curr and node distinct nodes -- shift 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;
    
}