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);
};
RB
? it's redundant and overly verbose. \$\endgroup\$ – TemplateRex Sep 14 '13 at 8:48prune
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. \$\endgroup\$ – Derrick Dec 31 '14 at 19:41