Created
July 31, 2018 20:52
-
-
Save paullewallencom/5c9aa1f5cbd8d6a978674c9a349f6b38 to your computer and use it in GitHub Desktop.
Treap
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 TREAP_H | |
#define TREAP_H | |
#include <climits> | |
#include "UniformRandom.h" | |
#include "dsexceptions.h" | |
#include <iostream> | |
using namespace std; | |
template <typename Comparable> | |
class Treap | |
{ | |
public: | |
Treap( ) | |
{ | |
nullNode = new TreapNode; | |
nullNode->left = nullNode->right = nullNode; | |
nullNode->priority = INT_MAX; | |
root = nullNode; | |
} | |
Treap( const Treap & rhs ) | |
{ | |
nullNode = new TreapNode; | |
nullNode->left = nullNode->right = nullNode; | |
nullNode->priority = INT_MAX; | |
root = clone( rhs.root ); | |
} | |
~Treap( ) | |
{ | |
makeEmpty( ); | |
delete nullNode; | |
} | |
Treap( Treap && rhs ) : root{ rhs.root }, nullNode{ rhs.nullNode } | |
{ | |
rhs.root = nullptr; | |
rhs.nullNode = nullptr; | |
} | |
Treap & operator=( const Treap & rhs ) | |
{ | |
Treap copy = rhs; | |
std::swap( *this, copy ); | |
return *this; | |
} | |
Treap & operator=( Treap && rhs ) | |
{ | |
std::swap( root, rhs.root ); | |
std::swap( nullNode, rhs.nullNode ); | |
return *this; | |
} | |
const Comparable & findMin( ) const | |
{ | |
if( isEmpty( ) ) | |
throw UnderflowException{ }; | |
TreapNode *ptr = root; | |
while( ptr->left != nullNode ) | |
ptr = ptr->left; | |
return ptr->element; | |
} | |
const Comparable & findMax( ) const | |
{ | |
if( isEmpty( ) ) | |
throw UnderflowException{ }; | |
TreapNode *ptr = root; | |
while( ptr->right != nullNode ) | |
ptr = ptr->right; | |
return ptr->element; | |
} | |
bool contains( const Comparable & x ) const | |
{ | |
TreapNode *current = root; | |
nullNode->element = x; | |
for( ; ; ) | |
{ | |
if( x < current->element ) | |
current = current->left; | |
else if( current->element < x ) | |
current = current->right; | |
else | |
return current != nullNode; | |
} | |
} | |
bool isEmpty( ) const | |
{ | |
return root == nullNode; | |
} | |
void printTree( ) const | |
{ | |
if( isEmpty( ) ) | |
cout << "Empty tree" << endl; | |
else | |
printTree( root ); | |
} | |
void makeEmpty( ) | |
{ | |
makeEmpty( root ); | |
} | |
void insert( const Comparable & x ) | |
{ | |
insert( x, root ); | |
} | |
void insert( Comparable && x ) | |
{ | |
insert( std::move( x ), root ); | |
} | |
void remove( const Comparable & x ) | |
{ | |
remove( x, root ); | |
} | |
private: | |
struct TreapNode | |
{ | |
Comparable element; | |
TreapNode *left; | |
TreapNode *right; | |
int priority; | |
TreapNode( ) : left{ nullptr }, right{ nullptr }, priority{ INT_MAX } { } | |
TreapNode( const Comparable & e, TreapNode *lt, TreapNode *rt, int pr ) | |
: element{ e }, left{ lt }, right{ rt }, priority{ pr } | |
{ } | |
TreapNode( Comparable && e, TreapNode *lt, TreapNode *rt, int pr ) | |
: element{ std::move( e ) }, left{ lt }, right{ rt }, priority{ pr } | |
{ } | |
}; | |
TreapNode *root; | |
TreapNode *nullNode; | |
UniformRandom randomNums; | |
void insert( const Comparable & x, TreapNode* & t ) | |
{ | |
if( t == nullNode ) | |
t = new TreapNode{ x, nullNode, nullNode, randomNums.nextInt( ) }; | |
else if( x < t->element ) | |
{ | |
insert( x, t->left ); | |
if( t->left->priority < t->priority ) | |
rotateWithLeftChild( t ); | |
} | |
else if( t->element < x ) | |
{ | |
insert( x, t->right ); | |
if( t->right->priority < t->priority ) | |
rotateWithRightChild( t ); | |
} | |
// else duplicate; do nothing | |
} | |
void insert( Comparable && x, TreapNode* & t ) | |
{ | |
if( t == nullNode ) | |
t = new TreapNode{ std::move( x ), nullNode, nullNode, randomNums.nextInt( ) }; | |
else if( x < t->element ) | |
{ | |
insert( std::move( x ), t->left ); | |
if( t->left->priority < t->priority ) | |
rotateWithLeftChild( t ); | |
} | |
else if( t->element < x ) | |
{ | |
insert( std::move( x ), t->right ); | |
if( t->right->priority < t->priority ) | |
rotateWithRightChild( t ); | |
} | |
// else duplicate; do nothing | |
} | |
void remove( const Comparable & x, TreapNode * & t ) | |
{ | |
if( t != nullNode ) | |
{ | |
if( x < t->element ) | |
remove( x, t->left ); | |
else if( t->element < x ) | |
remove( x, t->right ); | |
else | |
{ | |
// Match found | |
if( t->left->priority < t->right->priority ) | |
rotateWithLeftChild( t ); | |
else | |
rotateWithRightChild( t ); | |
if( t != nullNode ) // Continue on down | |
remove( x, t ); | |
else | |
{ | |
delete t->left; | |
t->left = nullNode; // At a leaf | |
} | |
} | |
} | |
} | |
void makeEmpty( TreapNode * & t ) | |
{ | |
if( t != nullNode ) | |
{ | |
makeEmpty( t->left ); | |
makeEmpty( t->right ); | |
delete t; | |
} | |
t = nullNode; | |
} | |
void printTree( TreapNode *t ) const | |
{ | |
if( t != nullNode ) | |
{ | |
printTree( t->left ); | |
cout << t->element << endl; | |
printTree( t->right ); | |
} | |
} | |
// Rotations | |
void rotateWithLeftChild( TreapNode * & k2 ) | |
{ | |
TreapNode *k1 = k2->left; | |
k2->left = k1->right; | |
k1->right = k2; | |
k2 = k1; | |
} | |
void rotateWithRightChild( TreapNode * & k1 ) | |
{ | |
TreapNode *k2 = k1->right; | |
k1->right = k2->left; | |
k2->left = k1; | |
k1 = k2; | |
} | |
TreapNode * clone( TreapNode * t ) const | |
{ | |
if( t == t->left ) // Cannot test against nullNode!!! | |
return nullNode; | |
else | |
return new TreapNode{ t->element, clone( t->left ), clone( t->right ), t->priority }; | |
} | |
}; | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment