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

• Loki Astari: Note: You do realize that std::set is usually implemented as a Red/Black tree.
• user473973: Yes, I know that (and I think some other std:: structures are too). But what I needed to do (for an honors project) was to implement a RB tree myself.
• TemplateRex: why are you prefixing every member function with RB? it's redundant and overly verbose.
• user473973: You're right. I only did it because that is how my class's book's implementation is done.
• Derrick: Take a look at my C++ intrusive red-black tree, which also implements node removal (called prune here). If you don't like intrusive trees, it is trivial (but an exercise for the reader) to make a non-intrusive container out of this container.

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.

• user473973: Thank you for all of this. I agree with all of it except I have a comment about one thing: the "nil" RBNode pointer is not supposed to be NULL, it was just an unfortunate name that my algorithms book decided to call that pointer.
• Olayinka: @user473973 the pointer is NULL, it is not pointing anywhere. This is why all null pointer of the same color regardless of their parents
• MAG: The nil node is used so it can be treated as any other node simplifying the the code's logic. The CLRS book uses this sentinel for convenience.