Instantly share code, notes, and snippets.

Embed
What would you like to do?
Top-Down Splay Tree
#ifndef SPLAY_TREE_H
#define SPLAY_TREE_H
#include "dsexceptions.h"
#include <iostream>
using namespace std;
template <typename Comparable>
class SplayTree
{
public:
SplayTree( )
{
nullNode = new BinaryNode;
nullNode->left = nullNode->right = nullNode;
root = nullNode;
}
SplayTree( const SplayTree & rhs )
{
nullNode = new BinaryNode;
nullNode->left = nullNode->right = nullNode;
root = clone( rhs.root );
}
SplayTree( SplayTree && rhs ) : root{ rhs.root }, nullNode{ rhs.nullNode }
{
rhs.root = nullptr;
rhs.nullNode = nullptr;
}
~SplayTree( )
{
makeEmpty( );
delete nullNode;
}
SplayTree & operator=( const SplayTree & rhs )
{
SplayTree copy = rhs;
std::swap( *this, copy );
return *this;
}
SplayTree & operator=( SplayTree && rhs )
{
std::swap( root, rhs.root );
std::swap( nullNode, rhs.nullNode );
return *this;
}
const Comparable & findMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };
BinaryNode *ptr = root;
while( ptr->left != nullNode )
ptr = ptr->left;
splay( ptr->element, root );
return ptr->element;
}
const Comparable & findMax( )
{
if( isEmpty( ) )
throw UnderflowException{ };
BinaryNode *ptr = root;
while( ptr->right != nullNode )
ptr = ptr->right;
splay( ptr->element, root );
return ptr->element;
}
bool contains( const Comparable & x )
{
if( isEmpty( ) )
return false;
splay( x, root );
return root->element == x;
}
bool isEmpty( ) const
{
return root == nullNode;
}
void printTree( ) const
{
if( isEmpty( ) )
cout << "Empty tree" << endl;
else
printTree( root );
}
void makeEmpty( )
{
while( !isEmpty( ) )
{
findMax( ); // Splay max item to root
remove( root->element );
}
}
void insert( const Comparable & x )
{
static BinaryNode *newNode = nullptr;
if( newNode == nullptr )
newNode = new BinaryNode;
newNode->element = x;
if( root == nullNode )
{
newNode->left = newNode->right = nullNode;
root = newNode;
}
else
{
splay( x, root );
if( x < root->element )
{
newNode->left = root->left;
newNode->right = root;
root->left = nullNode;
root = newNode;
}
else
if( root->element < x )
{
newNode->right = root->right;
newNode->left = root;
root->right = nullNode;
root = newNode;
}
else
return;
}
newNode = nullptr; // So next insert will call new
}
void remove( const Comparable & x )
{
// If x is found, it will be splayed to the root by contains
if( !contains( x ) )
return; // Item not found; do nothing
BinaryNode *newTree;
if( root->left == nullNode )
newTree = root->right;
else
{
// Find the maximum in the left subtree
// Splay it to the root; and then attach right child
newTree = root->left;
splay( x, newTree );
newTree->right = root->right;
}
delete root;
root = newTree;
}
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( ) : left{ nullptr }, right{ nullptr } { }
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element{ theElement }, left{ lt }, right{ rt } { }
};
BinaryNode *root;
BinaryNode *nullNode;
void reclaimMemory( BinaryNode * t )
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
void printTree( BinaryNode *t ) const
{
if( t != t->left )
{
printTree( t->left );
cout << t->element << endl;
printTree( t->right );
}
}
BinaryNode * clone( BinaryNode * t ) const
{
if( t == t->left ) // Cannot test against nullNode!!!
return nullNode;
else
return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
}
// Tree manipulations
void rotateWithLeftChild( BinaryNode * & k2 )
{
BinaryNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
void rotateWithRightChild( BinaryNode * & k1 )
{
BinaryNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
void splay( const Comparable & x, BinaryNode * & t )
{
BinaryNode *leftTreeMax, *rightTreeMin;
static BinaryNode header;
header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = &header;
nullNode->element = x; // Guarantee a match
for( ; ; )
if( x < t->element )
{
if( x < t->left->element )
rotateWithLeftChild( t );
if( t->left == nullNode )
break;
// Link Right
rightTreeMin->left = t;
rightTreeMin = t;
t = t->left;
}
else if( t->element < x )
{
if( t->right->element < x )
rotateWithRightChild( t );
if( t->right == nullNode )
break;
// Link Left
leftTreeMax->right = t;
leftTreeMax = t;
t = t->right;
}
else
break;
leftTreeMax->right = t->left;
rightTreeMin->left = t->right;
t->left = header.right;
t->right = header.left;
}
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment