Created
July 31, 2018 20:46
-
-
Save paullewallencom/d9d77bcabe41fcafbee4bc78b00f92b8 to your computer and use it in GitHub Desktop.
Top-Down Splay 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 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