Rotate_left and Rotate_right functions for a treap
Hi I have the following code for a treap but I don't know how to make roate_left and rotate_right functions to balance it. I need some explanations and some code. Thanks
Code:
#include<iostream>
#include<utility>
#include<stdlib.h>
#include<time.h>
#include<stdio.h>
using namespace std;
template<typename T> class Treap{
public:
unsigned int priority;
Treap<T> *root, *left, *right, *parent;
T *pinfo;
Treap()
{
priority = rand();
left = right = NULL;
root = this;
pinfo = NULL;
}
void insert(T x)
{
if (pinfo == NULL)
{
pinfo = new T;
*pinfo = x;
}
else
{
if (x<=*pinfo){
if (left == NULL){
left = new Treap<T>;
left->pinfo = new T;
*(left->pinfo) = x;
//balance(left);
left->left = left->right = NULL;
left->parent = this;
left->root = root;
}
else
left->insert(x);
}
else{
if (right == NULL)
{
right = new Treap<T>;
right->pinfo = new T;
*(right->pinfo) = x;
//balance(right);
right->left = right->right = NULL;
right->parent = this;
right->root = root;
}
else
right->insert(x);
}
}
}
Treap<T>* find(T x)
{
Treap<T> *rez;
if (pinfo == NULL)
return NULL;
if ((*pinfo) == x)
return this;
if (x <= (*pinfo))
{
if (left != NULL)
return left->find(x);
else
return NULL;
}
else
{
if (right != NULL)
return right->find(x);
else
return NULL;
}
}
void inOrderTraversal()
{
if (left != NULL)
left->inOrderTraversal();
//std::cout<<pinfo->first<<" "<<pinfo->second<<std::endl;
cout<<*pinfo<<" ";
if (right != NULL)
right->inOrderTraversal();
}
};
int main()
{
srand(23424);
Treap<int> *r = new Treap<int>;
r->insert(2);
r->insert(5);
r->insert(7);
r->insert(1);
r->insert(9);
r->inOrderTraversal();
return 0;
}
Re: Rotate_left and Rotate_right functions for a treap
