Top-Down Red Black Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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