Red Black Tree Insertion Not Working

Question

I'm working on a red black tree assignment for my class and I'm having some trouble with the insertion function. My problem is that my root node value is being changed somehow between the end of the insert function and the beginning of insert being called again. I ran it through the debugger in Visual Studio and saw no reason why the root key should be altered like it is. I'm sure there are many other errors in my code thus far because I decided to focus on this before the rest of the program. Once this is fixed I will go back and correct other errors. I have not yet implemented the fix-up function for correcting the tree after insertion so don't worry about red-black tree properties being met. If you have any questions or if I haven't given enough info then please let me know.

/ rbtree.cpp 

#include <iostream>
#include <iomanip>
#include "rbtree.h"

using std::cout;
using std::setw;
using std::endl;

void RBTree::reverseInOrderPrint(Node *x, int depth) {
   if ( x != nil ) {
      reverseInOrderPrint(x->right, depth+1);
      cout << setw(depth*4+4) << x->color << " ";
      cout << *(x->key) << " " << *(x->value) << endl;
      reverseInOrderPrint(x->left, depth+1);
   }
}


RBTree::RBTree()
{
    nil = new Node();
    root = nil;
}

RBTree::~RBTree()
{
    //delete[] root;    
}


void RBTree::rbInsert(const string& key_given, const string& value_given)
{
    //if(root != nil)
        //cout << *(root -> key) << " <- root key at beginning of insert function" << endl;


    Node* input_node = new Node(key_given, value_given, nil);
    Node* target = root;
    Node* target_parent = nil;



    while(target != nil)
    {

        target_parent = target;

        if(input_node -> key -> compare(*(target -> key)) < 0)
            target = target -> left;

        else
            target = target -> right;


    }


    input_node -> parent = target_parent;

    if(target_parent == nil)
        root = input_node;

    else if(input_node -> key -> compare(*(target_parent -> key)) < 0)
        target_parent -> left = input_node;

    else
        target_parent -> right = input_node;

    input_node -> left = nil;

    input_node -> right = nil;

    input_node -> color = 'R';

    /*rbInsertFixup(input_node);
    cout << *(root -> key) << " <- root key at end of insert function" << endl;
    if(root -> left != nil)
        cout << *(root -> left -> key) << " is root's left child" << endl;
    if(root -> right != nil)
        cout << *(root -> right -> key) << " is root's right child"  << endl;*/

}


//void RBTree::rbInsertFixup(



RBTree::Node::Node()
{
    parent = NULL;
    left = NULL;
    right = NULL;
    color = 'B';
    key = NULL;
    value = NULL;
}


RBTree::Node::Node(const string& key_given, const string& value_given, Node* nil_pntr)
{
    parent = nil_pntr;
    left = nil_pntr;
    right = nil_pntr;
    color = 'R';
    key = &key_given;
    value = &value_given;
}


RBTree::Node::~Node()
{
    if(left != NULL)
        delete left;
    if(right != NULL)
        delete right;

}

int main()
{
        RBTree tree;

        tree.rbInsert("Zack", "His Birthday");
        tree.rbInsert("Terri", "Her Birthdays");
        tree.rbInsert("Zzck", "HBD");

        return 0;
}

Here is an example of the output I get when running this code:

Zack <- root key at end of insert function
Terri <- root key at beginning of insert function
Terri <- root key at end of insert function
Terri is root's right child
Zzck <- root key at beginning of insert function
Zzck <- root key at end of insert function
Zzck is root's right child

Answer 1

you need to compare 2 strings, you have to dereference the input_node->key and because you are using compare to check the two strings try using "<" or ">" and i am pretty sure it will work have something like this * (input_node -> key) <*(target_parent -> key)