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