My Red-Black Tree Implementation

Question

I worked on a Red-Black tree implementation in C++, and it works as it should. However, I want to see what else I can do to make this code faster/more clean, etc.

Any particular suggestions?

Edit: code I want most looked at is below (insertion into the RBtree)

/******************************
 RBInsert
 Purpose: Insert a new datum into tree
 *******************************/
template <class T>
void RBTree<T>::RBinsert(T data) {
    RBNode<T>* x;
    RBNode<T>* y;
    RBNode<T>* temp = RBTree::search(data);

    if(temp != RBTree::nil) {
        cout << "Node already in Tree!" << endl;
        return;
    }
    RBNode<T>* z = new RBNode<T>();
    z->data = data;
    y = this->RBTree::nil;
    x = this->root;
    while(x != RBTree::nil) {
        y = x;
        if (z->data < x->data)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if(y == RBTree::RBTree::nil)
        root = z;
    else if(z->data < y->data)
        y->left = z;
    else
        y->right = z;
    z->left = RBTree::nil;
    z->right = RBTree::nil;
    z->changeColor(RBNode<T>::red);
    RBTree::RBinsertFixup(z);
}

/******************************
 RBinsertFixup
 Purpose: After inserting, calls this
to fix red-black properties of tree
 *******************************/
template <class T>
void RBTree<T>::RBinsertFixup(RBNode<T>* z) {
    RBNode<T>* y;
    while(z->parent->color == RBNode<T>::red && z->parent != RBTree::nil) {
        if(z->parent == z->parent->parent->left) {
        y = z->parent->parent->right;

        // Case 1
        if(y->color == RBNode<T>::red) {
            z->parent->changeColor(RBNode<T>::black);
            y->changeColor(RBNode<T>::black);
            z->parent->parent->changeColor(RBNode<T>::red);
            z = z->parent->parent;
        } else {

            // Case 2
            if(z == z->parent->right) {
                z = z->parent;
                leftRotate(z);
            }

            // Case 3
            z->parent->changeColor(RBNode<T>::black);
            z->parent->parent->changeColor(RBNode<T>::red);
            rightRotate(z->parent->parent);
        }
    } else {
        y = z->parent->parent->left;

        // Case 1
            if(y->color == RBNode<T>::red) {
                z->parent->changeColor(RBNode<T>::black);
                y->changeColor(RBNode<T>::black);
                z->parent->parent->changeColor(RBNode<T>::red);
                z = z->parent->parent;
            } else {

                // Case 2
                if(z == z->parent->left) {
                    z = z->parent;
                    rightRotate(z);
                }

                // Case 3
                z->parent->changeColor(RBNode<T>::black);
                z->parent->parent->changeColor(RBNode<T>::red);
                leftRotate(z->parent->parent);
            }
        }
    }
    root->changeColor(RBNode<T>::black);
}

Edit: Adding RBTree class declaration:

#include <fstream>
#include <iostream>
#include "RBNode.h"

using std::ifstream;

template <class T>
class RBTree {
public:
    RBTree();
    ~RBTree();

    void RBwrite(RBNode<T>*);
    void RBread();
    void RBinsert(T);
    void RBdelete(T);

    RBNode<T>* getRoot() { return root; }

private:
    bool treeCreated = false;

    RBNode<T>* nil;
    RBNode<T>* root;

    RBNode<T>* minimum(RBNode<T>*);

    void RBinsert(typename RBNode<T>::Color, T);
    void RBinsertFixup(RBNode<T>*);
    void RBdeleteFixup(RBNode<T>*);
    void transplant(RBNode<T>*, RBNode<T>*);

    void leftRotate(RBNode<T>*);
    void rightRotate(RBNode<T>*);

    void deleteHelper(RBNode<T>* temp);

    RBNode<T>* search(T);
};

Answer 1

Its hard to review because you did not provide enough to compile.

DON'T use using in a header file that is just the global namespace.

using std::ifstream;

This would have been fine if you had placed your stuff in your own namespace. But because it is in global namespace your choices affect other people. ie. Your code could potentially break my code.

The prefix RB is unnecessary and very C like. You should really use your own namespace RB as this resolves the same issue that you are trying to avoid. I notice from the above comments that you got this idea from a book. I would advice this book is way out of date as modern C++ books would not use this style.

Interface:

void RBwrite(RBNode<T>*);

I don't understand what this is for.
Are you asking this tree to write out another tree? If you are asking the class to serialize the tree then I migth see it but then I would make the function static. But then I have to ask write it to where? You should be providing a location to stream the data.

Personally I would replace the above call with:

friend std::ostream& operator<<(std::ostream& stream, RBTree<T> const& data)
{
    // write tree to stream
    // Internally you can call RBWrite() but passing a stream
    // I would make RBWrite private
} 

Then the converse:

void RBread();

Again where are you reading from? Again I would change the interface:

friend std::istream& operator>>(std::istream& stream, RBTree<T>& data)
{
    // read tree from stream
    // Internally you can call RBRead() but passing a stream
    // I would make RBRead private
} 

With the changes in the interface you are more C++ like.

Potential Syntax Errors;

 bool treeCreated = false;

This does not compile in C++98 (though it is valid C++11). But worse it suggests that a tree can be in an uncreated state. Once the constructor is finished the object should be fully formed and ready for use. If the constructor fails you should throw an exception to make sure that you do not have an invalid object.

Design:

RBNode<T>* nil;

Is this supposed to represent a NULL pointer?
If so prefer NULL. Or if you are using C++11 or later then use nullptr.

Usage

void RBTree<T>::RBinsert(T data) {
    RBNode<T>* x;
    RBNode<T>* y;

Declare variables where they are used. Declaring variables at the top of the function is a C style. In C++ you declare variables at the point they are being used (or as close to that point as possible).

Two line initialization?

RBNode<T>* z = new RBNode<T>();
z->data = data;

Your constructor for a RBNode can be passed the data object and allow one line initialization. Reading further into the function I would go even further. This whole function can be simplified by moving the node initialization into its construtor of RBNode.

void RBTree<T>::RBinsert(T data)
{
    RBNode<T>* temp = RBTree::search(data);

    if(temp != RBTree::nil) {
        cout << "Node already in Tree!" << endl;
        return;
    }

    RBNode<T>* y = this->RBTree::nil;
    RBNode<T>* x = this->root;

    while(x != RBTree::nil) {
        y = x;
        x = (data < x->data) ? x->left : x->right;
    }

    RBNode<T>* z = new RBNode<T>(data, y); // Node knows to set itself to RED if
                                           // y is not NULL Green otherwise
    if(y == RBTree::RBTree::nil) {
        root = z;
    } else {
        RBTree::RBinsertFixup(z);          // Only re-balance if not the first node
    }
}

I forget how to do the rotation for a Red/Black tree (that's why I have a copy of Knuth). But it looks fine.