C++ Programming Code Examples C++ > Data Structures and Algorithm Analysis in C++ Code Examples Implementation for top-down red black tree Implementation for top-down red black tree #include "RedBlackTree.h" /** * Construct the tree. * negInf is a value less than or equal to all others. * It is also used as ITEM_NOT_FOUND. */ template <class Comparable> RedBlackTree<Comparable>::RedBlackTree( const Comparable & negInf ) : ITEM_NOT_FOUND( negInf ) { nullNode = new RedBlackNode<Comparable>; nullNode->left = nullNode->right = nullNode; header = new RedBlackNode<Comparable>( negInf ); header->left = header->right = nullNode; } /** * Copy constructor. */ template <class Comparable> RedBlackTree<Comparable>::RedBlackTree( const RedBlackTree<Comparable> & rhs ) : ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND ) { nullNode = new RedBlackNode<Comparable>; nullNode->left = nullNode->right = nullNode; header = new RedBlackNode<Comparable>( ITEM_NOT_FOUND ); header->left = header->right = nullNode; *this = rhs; } /** * Destroy the tree. */ template <class Comparable> RedBlackTree<Comparable>::~RedBlackTree( ) { makeEmpty( ); delete nullNode; delete header; } /** * Insert item x into the tree. Does nothing if x already present. */ template <class Comparable> void RedBlackTree<Comparable>::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<Comparable>( x, nullNode, nullNode ); // Attach to parent if( x < parent->element ) parent->left = current; else parent->right = current; handleReorient( x ); } /** * Remove item x from the tree. * Not implemented in this version. */ template <class Comparable> void RedBlackTree<Comparable>::remove( const Comparable & x ) { cout << "Sorry, remove unimplemented; " << x << " still present" << endl; } /** * Find the smallest item the tree. * Return the smallest item or ITEM_NOT_FOUND if empty. */ template <class Comparable> const Comparable & RedBlackTree<Comparable>::findMin( ) const { if( isEmpty( ) ) return ITEM_NOT_FOUND; RedBlackNode<Comparable> *itr = header->right; while( itr->left != nullNode ) itr = itr->left; return itr->element; } /** * Find the largest item in the tree. * Return the largest item or ITEM_NOT_FOUND if empty. */ template <class Comparable> const Comparable & RedBlackTree<Comparable>::findMax( ) const { if( isEmpty( ) ) return ITEM_NOT_FOUND; RedBlackNode<Comparable> *itr = header->right; while( itr->right != nullNode ) itr = itr->right; return itr->element; } /** * Find item x in the tree. * Return the matching item or ITEM_NOT_FOUND if not found. */ template <class Comparable> const Comparable & RedBlackTree<Comparable>::find( const Comparable & x ) const { nullNode->element = x; RedBlackNode<Comparable> *curr = header->right; for( ; ; ) { if( x < curr->element ) curr = curr->left; else if( curr->element < x ) curr = curr->right; else if( curr != nullNode ) return curr->element; else return ITEM_NOT_FOUND; } } /** * Make the tree logically empty. */ template <class Comparable> void RedBlackTree<Comparable>::makeEmpty( ) { reclaimMemory( header->right ); header->right = nullNode; } /** * Test if the tree is logically empty. * Return true if empty, false otherwise. */ template <class Comparable> bool RedBlackTree<Comparable>::isEmpty( ) const { return header->right == nullNode; } /** * Print the tree contents in sorted order. */ template <class Comparable> void RedBlackTree<Comparable>::printTree( ) const { if( header->right == nullNode ) cout << "Empty tree" << endl; else printTree( header->right ); } /** * Deep copy. */ template <class Comparable> const RedBlackTree<Comparable> & RedBlackTree<Comparable>::operator=( const RedBlackTree<Comparable> & rhs ) { if( this != &rhs ) { makeEmpty( ); header->right = clone( rhs.header->right ); } return *this; } /** * Internal method to print a subtree t in sorted order. */ template <class Comparable> void RedBlackTree<Comparable>::printTree( RedBlackNode<Comparable> *t ) const { if( t != t->left ) { printTree( t->left ); cout << t->element << endl; printTree( t->right ); } } /** * Internal method to clone subtree. */ template <class Comparable> RedBlackNode<Comparable> * RedBlackTree<Comparable>::clone( RedBlackNode<Comparable> * t ) const { if( t == t->left ) // Cannot test against nullNode!!! return nullNode; else return new RedBlackNode<Comparable>( t->element, clone( t->left ), clone( t->right ), t->color ); } /** * Internal routine that is called during an insertion * if a node has two red children. Performs flip * and rotatons. * item is the item being inserted. */ template <class Comparable> void RedBlackTree<Comparable>::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 } /** * Internal routine that performs a single or double rotation. * Because the result is attached to the parent, there are four cases. * Called by handleReorient. * item is the item in handleReorient. * parent is the parent of the root of the rotated subtree. * Return the root of the rotated subtree. */ template <class Comparable> RedBlackNode<Comparable> * RedBlackTree<Comparable>::rotate( const Comparable & item, RedBlackNode<Comparable> *theParent ) const { 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; } } /** * Rotate binary tree node with left child. */ template <class Comparable> void RedBlackTree<Comparable>:: rotateWithLeftChild( RedBlackNode<Comparable> * & k2 ) const { RedBlackNode<Comparable> *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2 = k1; } /** * Rotate binary tree node with right child. */ template <class Comparable> void RedBlackTree<Comparable>:: rotateWithRightChild( RedBlackNode<Comparable> * & k1 ) const { RedBlackNode<Comparable> *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1 = k2; } /** * Internal method to reclaim internal nodes * in subtree t. */ template <class Comparable> void RedBlackTree<Comparable>::reclaimMemory( RedBlackNode<Comparable> *t ) const { if( t != t->left ) { reclaimMemory( t->left ); reclaimMemory( t->right ); delete t; } }
