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