2
\$\begingroup\$

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);
    }

};
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jamal Oct 29 '13 at 18:36
  • \$\begingroup\$ ok @Jamal. All what I need from the Three is the Insert and AccessNode Functions. \$\endgroup\$ – Hani Gotc Oct 29 '13 at 19:40
  • \$\begingroup\$ Is the bool operator>(const Keys& rhs){ return rhs.word < word; } in the Key structure correct? \$\endgroup\$ – Hani Gotc Oct 29 '13 at 19:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Hani Gotc Oct 29 '13 at 19:52
  • \$\begingroup\$ 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 \$\endgroup\$ – Hani Gotc Oct 29 '13 at 19:53
3
\$\begingroup\$
  • 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); }
    
  • Prefer std::size_type over size_t for the vector's loop counter type:

    // 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.

\$\endgroup\$
2
\$\begingroup\$

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);
if (itr != mtStorade.cend())
    cout << itr->second << endl;
\$\endgroup\$
  • \$\begingroup\$ Thank you. Your suggestion is great. I am actually using multimap which allows duplicates. map won't allow it. \$\endgroup\$ – Hani Gotc Nov 5 '13 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.