Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement