# Building a Red Black tree using a structure as a node

I have the following structure:

struct Keys
{
//value of word in the vector<string> words.
string word;
//index of word in the vector<string> words.
int index;
//I want to compare the element **word** of the structure, this is why i overloaded the operators
//After Editing
bool operator>(const Keys& rhs) const { return  word > rhs.word; }
bool operator==(const Keys& rhs) const { return word == rhs.word; }

};


I want to insert this structure into a Red Black tree, then I want to search for a given word and print its index.

int main()
{
kreb = new RedBlackTree<Keys>();
vector<string> words;
words.push_back("hello");
words.push_back("how");
words.push_back("are");
words.push_back("you");

for(size_t i = 0; i < words.size(); i++)
{
kreb->InsertNode({words[i],i});
}

string w = "hello";
//if word is found
if(kreb->AccessNode({w,0}) != 0)
{
cout << kreb->AccessNode({w,0})->GetValue().index << endl;
}
}


Instead of inserting integers into the red black tree, I want to insert a structure. In the structure, I've overloaded the operators > and == to be able to compare the structure objects in the red black tree (or whatever it is called).

What do you think? I am new to C++ and I want to be sure that I am doing it correctly.

Red-Black Tree Code:

#include <queue>
#include <stack>
#include <windows.h> //for coloring output only

using namespace std;

template <class T> class RBNode
{
private:
bool isRed;
T value;
RBNode<T> *left, *right, *parent;
public:
//Node()
//{
//  left = NULL;
//  right = NULL;
//}
RBNode(T value)
{
this->isRed = true;
this->value = value;
left = NULL;
right = NULL;
parent = NULL;
}
void Recolor()
{
if (this->isRed) this->isRed = false;
else this->isRed = true;
}
bool IsRed()
{
return isRed;
}
T GetValue()
{
return this->value;
}
RBNode* GetLeft()
{
return this->left;
}
RBNode* GetRight()
{
return this->right;
}
RBNode* GetParent()
{
return this->parent;
}
void ClearParent()
{
this->parent = NULL;
}
void SetLeft(RBNode* left)
{
this->left = left;
if(left != NULL) left->parent = this;
}
void SetRight(RBNode* right)
{
this->right = right;
if(right != NULL) right->parent = this;
}
};

template <class T> class RedBlackTree
{
private:
RBNode<T>* root;

//the three basic functionalities (inner implementation)
RBNode<T>* AccessNode(RBNode<T> *root, T value)
{
if(root->GetValue() == value)
{
return root;
}
else if(root->GetValue() > value)
{
if(root->GetLeft() == NULL)
{
return NULL;
}
else
{
return this->AccessNode(root->GetLeft(), value);
}
}
else
{
if(root->GetRight() == NULL)
{
return NULL;
}
else
{
return this->AccessNode(root->GetRight(), value);
}
}
}
void InsertNode(RBNode<T> *root, T value)
{
//regular BST insert
RBNode<T>* insertedNode = NULL;
if(root->GetValue() == value)
{
//skip
}
else if(root->GetValue() > value)
{
if(root->GetLeft() == NULL)
{
insertedNode = new RBNode<T>(value);
root->SetLeft(insertedNode);
}
else
{
this->InsertNode(root->GetLeft(), value);
}
}
else
{
if(root->GetRight() == NULL)
{
insertedNode = new RBNode<T>(value);
root->SetRight(insertedNode);
}
else
{
this->InsertNode(root->GetRight(), value);
}
}
//restore uniform black height
if (insertedNode == NULL) return;
this->SolveDoubleRedProblem(root);
insertedNode = NULL;
}

public:
RedBlackTree()
{
this->root = NULL;
}
bool IsEmpty()
{
return root == NULL;
}

//the three basic functionalities (clients interface)
RBNode<T>* AccessNode(T value)
{
if (this->IsEmpty()) return NULL;
else return this->AccessNode(root, value);
}
void InsertNode(T value)
{
if (this->IsEmpty())
{
this->root = new RBNode<T>(value);
this->root->Recolor();
}
else this->InsertNode(this->root, value);
}

};

• I'm getting an auto-flag saying that this is excessively long. You could probably split the red-black code into different parts, or just leave out some portion of it. Just keep whatever you absolutely need reviewed. – Jamal Oct 29 '13 at 18:36
• ok @Jamal. All what I need from the Three is the Insert and AccessNode Functions. – Hani Gotc Oct 29 '13 at 19:40
• Is the bool operator>(const Keys& rhs){ return rhs.word < word; } in the Key structure correct? – Hani Gotc Oct 29 '13 at 19:41
• ok no problem. See @Jamal what i am doing is inserting Objects into the tree instead for example of integers and strings only. and I am comparing the objects by using Word. – Hani Gotc Oct 29 '13 at 19:52
• the Tree class is not important. I am sure that it's right. I just need to know if the Operators > and == are right. And If can use another structure – Hani Gotc Oct 29 '13 at 19:53

• operator> and operator== are correct, but you should also define their complements. Users may also expect an operator< and an operator!=:

bool operator<(const Keys& rhs) const { return word < rhs.word; }


bool operator!=(const Keys& rhs) const { return !(word == rhs.word); }

• // template type depending on specific vector type
std::vector<std::string>::size_type;


This will allow you to access the entire vector, regardless of its size. std::size_type is also portable as it is defined as part of each STL container.

• Prefer nullptr to NULL if using C++11.

• Member functions that don't modify data members should be const. This would include the "getters" and those that return bool.

• The this-> is not needed everywhere as the current object is already in scope. However, you will need it if a parameter shares the same name as a data member (commonly found in a constructor). Then, you'll need the this-> to refer to the data member.

• RBNode() and RedBlackTree():

RBNode(T value)
{
this->isRed = true;
this->value = value;
left = NULL;
right = NULL;
parent = NULL;
}


RedBlackTree()
{
this->root = NULL;
}


should be initializer lists:

// could still be written vertically
//   to make list easier to maintain
RBNode(T value)
: isRed(true)
, value(value)
, left(NULL)
, right(NULL)
, parent(NULL)
{}


RedBlackTree() : root(NULL) {}

• You have this in main():

kreb = new RedBlackTree<Keys>();


...but no delete anywhere! Whenever you use new, you must use delete appropriately, otherwise you'll cause a memory leak. C++ doesn't have a garbage collector.

You already use std::vector in your example, so then why don't you use std::map? All known std::map implementations are red-black tree based.

Example:

typedef map<string, int> RedBlackTree;
RedBlackTree myStorage;

for(size_t i = 0; i < words.size(); i++)
myStorage.emplace(words[i], i);

string w = "hello";
auto itr = myStorage.find(w);

• Thank you. Your suggestion is great. I am actually using multimap which allows duplicates. map won't allow it. – Hani Gotc Nov 5 '13 at 14:01