RST.hpp
#ifndef RST_HP
#define RST_HPP
#include "BST.hpp"
#include "RSTNode.hpp"
/*
set expandtab
set shiftwidth=2
set softtabstop=2
gg=G
*/
template <typename Data>
class RST : public BST<Data> {
public:
virtual bool insert(const Data& item) {
if (addToTree(this->root, NULL, item))
{
this->isize++;
//perform rotations
return true;
}
else
return false;
}
virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) {
//this is assuming the right child is of higher priority than the parent
RSTNode<Data>* dummyone = ptr;
RSTNode<Data>* dummytwo = ptr->parent;
RSTNode<Data>* dummythree = ptr->parent->parent;
bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent);
//need to bring up priority and maintain binary tree property
if(dummyone->priority > dummyone->parent->priority) {
if(isTheFatherToTheRightOfTheGrandParent){
ptr->parent->parent->right = dummyone;
ptr->left = dummytwo;
}
if(!isTheFatherToTheRightOfTheGrandParent){
ptr->parent->parent->left = ptr;
ptr->left = dummytwo;
}
}
}
virtual void rightRotate(RSTNode<Data>*& ptr) {
return;
}
virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num)
{
if (ptr!=NULL)
{
if (num < ptr->data)
{
temp = ptr;
addToTree(ptr->left, temp, num);
}
else if (ptr->data < num)
{
temp = ptr;
addToTree(ptr->right, temp, num);
}
else
return false;
}
else
{
ptr = new RSTNode<Data>(num);
ptr->parent = temp;
return true;
}
}
};
#endif // RST_HPP
RSTNode.hpp
#ifndef RSTNODE_HPP
#define RSTNODE_HPP
#include "BSTNode.hpp"
//for random #
#include <cstdlib>
template <typename Data>
class RSTNode : public BSTNode<Data> {
public:
RSTNode(Data const & d) : BSTNode<Data>(d) {
srand((unsigned)time(0));
priority = rand();
left = right = parent = 0;
}
int const priority;
};
#endif // RSTNODE_HPP
the above should give enough info but just incase
BSTNode.hpp
#ifndef BSTNODE_HPP
#define BSTNODE_HPP
#include <iostream>
#include <iomanip>
template<typename Data>
class BSTNode {
public:
/** Constructor. Initialize a BSTNode with the given Data item,
* no parent, and no children.
*/
BSTNode(const Data & d) : data(d) {
left = right = parent = 0;
}
BSTNode<Data>* left;
BSTNode<Data>* right;
BSTNode<Data>* parent;
Data const data; // the const Data in this node.
/** Return the successor of this BSTNode in a BST, or 0 if none.
** PRECONDITION: this BSTNode is a node in a BST.
** POSTCONDITION: the BST is unchanged.
** RETURNS: the BSTNode that is the successor of this BSTNode,
** or 0 if there is none.
*/ // TODO
BSTNode<Data>* successor() {
BSTNode<Data>* cursor;
BSTNode<Data>* par;
cursor = this->right;
par = this->parent;
if (this->right != NULL)
{
while (cursor->left != NULL) {
cursor = cursor->left;
}
return cursor;
}
if ((this->right == NULL) && (this == par->left))
return this->parent;
if ((this->right == NULL) && (this == par->right))
{
do
{
cursor = par;
par = par->parent;
if (par == NULL)
{return cursor;}
}while(cursor != par->left);
return par;
}
if (this->right == NULL && this->parent == NULL)
return NULL;
}
};
/** Overload operator<< to print a BSTNode's fields to an ostream. */
template <typename Data>
std::ostream & operator<<(std::ostream& stm, const BSTNode<Data> & n) {
stm << '[';
stm << std::setw(10) << &n; // address of the BSTNode
stm << "; p:" << std::setw(10) << n.parent; // address of its parent
stm << "; l:" << std::setw(10) << n.left; // address of its left child
stm << "; r:" << std::setw(10) << n.right; // address of its right child
stm << "; d:" << n.data; // its data field
stm << ']';
return stm;
}
#endif // BSTNODE_HPP
RST.hpp
#ifndef RST_HP
#define RST_HPP
#include "BST.hpp"
/*
set expandtab
set shiftwidth=2
set softtabstop=2
gg=G
*/
template <typename Data>
class RST : public BST<Data> {
public:
virtual bool insert(const Data& item) {
if (addToTree(this->root, NULL, item))
{
this->isize++;
//perform rotations
return true;
}
else
return false;
}
virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) {
//this is assuming the right child is of higher priority than the parent
RSTNode<Data>* dummyone = ptr;
RSTNode<Data>* dummytwo = ptr->parent;
RSTNode<Data>* dummythree = ptr->parent->parent;
bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent);
//need to bring up priority and maintain binary tree property
if(dummyone->priority > dummyone->parent->priority) {
if(isTheFatherToTheRightOfTheGrandParent){
ptr->parent->parent->right = dummyone;
ptr->left = dummytwo;
}
if(!isTheFatherToTheRightOfTheGrandParent){
ptr->parent->parent->left = ptr;
ptr->left = dummytwo;
}
}
}
virtual void rightRotate(RSTNode<Data>*& ptr) {
return;
}
virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num)
{
if (ptr!=NULL)
{
if (num < ptr->data)
{
temp = ptr;
addToTree(ptr->left, temp, num);
}
else if (ptr->data < num)
{
temp = ptr;
addToTree(ptr->right, temp, num);
}
else
return false;
}
else
{
ptr = new RSTNode<Data>(num);
ptr->parent = temp;
return true;
}
}
};
#endif // RST_HPP