-
May 23rd, 2013, 02:24 AM
#1
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;
}
-
May 23rd, 2013, 12:34 PM
#2
Re: Rotate_left and Rotate_right functions for a treap
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|