Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Top-Down Red Black Tree
#ifndef RED_BLACK_TREE_H
#define RED_BLACK_TREE_H
#include "dsexceptions.h"
#include <iostream>
using namespace std;
template <typename Comparable>
class RedBlackTree
{
public:
explicit RedBlackTree( const Comparable & negInf )
{
nullNode = new RedBlackNode;
nullNode->left = nullNode->right = nullNode;
header = new RedBlackNode{ negInf };
header->left = header->right = nullNode;
}
RedBlackTree( const RedBlackTree & rhs )
{
nullNode = new RedBlackNode;
nullNode->left = nullNode->right = nullNode;
header = new RedBlackNode{ rhs.header->element };
header->left = nullNode;
header->right = clone( rhs.header->right );
}
RedBlackTree( RedBlackTree && rhs )
: nullNode{ rhs.nullNode }, header{ rhs.header }
{
rhs.nullNode = nullptr;
rhs.header = nullptr;
}
~RedBlackTree( )
{
makeEmpty( );
delete nullNode;
delete header;
}
RedBlackTree & operator=( const RedBlackTree & rhs )
{
RedBlackTree copy = rhs;
std::swap( *this, copy );
return *this;
}
RedBlackTree & operator=( RedBlackTree && rhs )
{
std::swap( header, rhs.header );
std::swap( nullNode, rhs.nullNode );
return *this;
}
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
RedBlackNode *itr = header->right;
while( itr->left != nullNode )
itr = itr->left;
return itr->element;
}
const Comparable & findMax( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
RedBlackNode *itr = header->right;
while( itr->right != nullNode )
itr = itr->right;
return itr->element;
}
bool contains( const Comparable & x ) const
{
nullNode->element = x;
RedBlackNode *curr = header->right;
for( ; ; )
{
if( x < curr->element )
curr = curr->left;
else if( curr->element < x )
curr = curr->right;
else
return curr != nullNode;
}
}
bool isEmpty( ) const
{
return header->right == nullNode;
}
void printTree( ) const
{
if( header->right == nullNode )
cout << "Empty tree" << endl;
else
printTree( header->right );
}
void makeEmpty( )
{
if( header == nullptr )
return;
reclaimMemory( header->right );
header->right = nullNode;
}
void insert( const Comparable & x )
{
current = parent = grand = header;
nullNode->element = x;
while( current->element != x )
{
great = grand; grand = parent; parent = current;
current = x < current->element ? current->left : current->right;
// Check if two red children; fix if so
if( current->left->color == RED && current->right->color == RED )
handleReorient( x );
}
// Insertion fails if already present
if( current != nullNode )
return;
current = new RedBlackNode{ x, nullNode, nullNode };
// Attach to parent
if( x < parent->element )
parent->left = current;
else
parent->right = current;
handleReorient( x );
}
void remove( const Comparable & x )
{
cout << "Sorry, remove unimplemented; " << x <<
" still present" << endl;
}
private:
enum { RED, BLACK };
struct RedBlackNode
{
Comparable element;
RedBlackNode *left;
RedBlackNode *right;
int color;
RedBlackNode( const Comparable & theElement = Comparable{ },
RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,
int c = BLACK )
: element{ theElement }, left{ lt }, right{ rt }, color{ c } { }
RedBlackNode( Comparable && theElement, RedBlackNode *lt = nullptr,
RedBlackNode *rt = nullptr, int c = BLACK )
: element{ std::move( theElement ) }, left{ lt }, right{ rt }, color{ c } { }
};
RedBlackNode *header; // The tree header (contains negInf)
RedBlackNode *nullNode;
// Used in insert routine and its helpers (logically static)
RedBlackNode *current;
RedBlackNode *parent;
RedBlackNode *grand;
RedBlackNode *great;
// Usual recursive stuff
void reclaimMemory( RedBlackNode *t )
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
void printTree( RedBlackNode *t ) const
{
if( t != t->left )
{
printTree( t->left );
cout << t->element << endl;
printTree( t->right );
}
}
RedBlackNode * clone( RedBlackNode * t ) const
{
if( t == t->left ) // Cannot test against nullNode!!!
return nullNode;
else
return new RedBlackNode{ t->element, clone( t->left ),
clone( t->right ), t->color };
}
void handleReorient( const Comparable & item )
{
// Do the color flip
current->color = RED;
current->left->color = BLACK;
current->right->color = BLACK;
if( parent->color == RED ) // Have to rotate
{
grand->color = RED;
if( item < grand->element != item < parent->element )
parent = rotate( item, grand ); // Start dbl rotate
current = rotate( item, great );
current->color = BLACK;
}
header->right->color = BLACK; // Make root black
}
RedBlackNode * rotate( const Comparable & item, RedBlackNode *theParent )
{
if( item < theParent->element )
{
item < theParent->left->element ?
rotateWithLeftChild( theParent->left ) : // LL
rotateWithRightChild( theParent->left ) ; // LR
return theParent->left;
}
else
{
item < theParent->right->element ?
rotateWithLeftChild( theParent->right ) : // RL
rotateWithRightChild( theParent->right ); // RR
return theParent->right;
}
}
void rotateWithLeftChild( RedBlackNode * & k2 )
{
RedBlackNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
void rotateWithRightChild( RedBlackNode * & k1 )
{
RedBlackNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment