Treap code:
Treap - main.c file
#include
#include
//#include"dot.c"
struct treap;
typedef struct treap * TREAP;
TREAP genRandTreap(TREAP , int);
TREAP autodelRoot(TREAP, int);
void dispInDotty(TREAP, FILE *);
/*void menu()
{
printf("\n0. Menu 1. Insert 2. Delete 3. Display\n");
}
int main()
{
int choice, l = 0, key;
TREAP t = NULL;
do
{
printf("\nEnter choice: ");
scanf("%d", &choice);
switch(choice)
{
case 0: menu(); break;
case 1: t = (TREAP)insert(t, getnode()); break;
case 2: printf("\nEnter key to delete: ");
scanf("%d", &key);
t = (TREAP)delete(t, search(t, key)); break;
case 3: dispTree(t); break;
}
}
while (l == 0);
return 0;
}*/
int main(int argc, char **argv)
{
TREAP t = NULL, temp = NULL;
int low = 10000, high = 100000, range = 10000, n;
struct timeval startTime, endTime;
double runTime;
FILE *insp, *delp, *dotty;
insp = fopen("treap.Ins.dat", "w");
delp = fopen("treap.Del.dat", "w");
dotty = fopen("treap.dot", "w");
fprintf(dotty, "digraph treap {");
if (argc >= 3)
{ low = atoi(argv[1]);
high = atoi(argv[2]);
if (argc == 4)
range = atoi(argv[3]);
}
printf("Low: %d, High: %d, Offset: %d\n", low, high, range);
printf("Nodes Created | Time Taken\tDeleted nodes out of nodes | Time taken\n");
for (n = low; n < high; n = n + range) // creates treap with 'n' nodes and deletes it
{
gettimeofday(&startTime, NULL);
t = genRandTreap(t, n);
gettimeofday(&endTime, NULL);
runTime = (endTime.tv_sec * 1000 + endTime.tv_usec / 1000) - (startTime.tv_sec * 1000 + startTime.tv_usec / 1000);
printf(" %d\t %.0lf ", n, runTime);
fprintf(insp,"%d\t%.0lf\n", n, runTime);
if (n == low)
dispInDotty(t, dotty);
gettimeofday(&startTime, NULL);
t = autodelRoot(t, n);
gettimeofday(&endTime, NULL);
runTime = (endTime.tv_sec * 1000 + endTime.tv_usec / 1000) - (startTime.tv_sec * 1000 + startTime.tv_usec / 1000);
printf(" of %d\t %.0lf\n", n, runTime);
fprintf(delp, "\n%d\t%.0lf", n, runTime);
}
fprintf(dotty, "}");
fclose(insp);
fclose(delp);
return 0;
}
#include
//#include"dot.c"
struct treap;
typedef struct treap * TREAP;
TREAP genRandTreap(TREAP , int);
TREAP autodelRoot(TREAP, int);
void dispInDotty(TREAP, FILE *);
/*void menu()
{
printf("\n0. Menu 1. Insert 2. Delete 3. Display\n");
}
int main()
{
int choice, l = 0, key;
TREAP t = NULL;
do
{
printf("\nEnter choice: ");
scanf("%d", &choice);
switch(choice)
{
case 0: menu(); break;
case 1: t = (TREAP)insert(t, getnode()); break;
case 2: printf("\nEnter key to delete: ");
scanf("%d", &key);
t = (TREAP)delete(t, search(t, key)); break;
case 3: dispTree(t); break;
}
}
while (l == 0);
return 0;
}*/
int main(int argc, char **argv)
{
TREAP t = NULL, temp = NULL;
int low = 10000, high = 100000, range = 10000, n;
struct timeval startTime, endTime;
double runTime;
FILE *insp, *delp, *dotty;
insp = fopen("treap.Ins.dat", "w");
delp = fopen("treap.Del.dat", "w");
dotty = fopen("treap.dot", "w");
fprintf(dotty, "digraph treap {");
if (argc >= 3)
{ low = atoi(argv[1]);
high = atoi(argv[2]);
if (argc == 4)
range = atoi(argv[3]);
}
printf("Low: %d, High: %d, Offset: %d\n", low, high, range);
printf("Nodes Created | Time Taken\tDeleted nodes out of nodes | Time taken\n");
for (n = low; n < high; n = n + range) // creates treap with 'n' nodes and deletes it
{
gettimeofday(&startTime, NULL);
t = genRandTreap(t, n);
gettimeofday(&endTime, NULL);
runTime = (endTime.tv_sec * 1000 + endTime.tv_usec / 1000) - (startTime.tv_sec * 1000 + startTime.tv_usec / 1000);
printf(" %d\t %.0lf ", n, runTime);
fprintf(insp,"%d\t%.0lf\n", n, runTime);
if (n == low)
dispInDotty(t, dotty);
gettimeofday(&startTime, NULL);
t = autodelRoot(t, n);
gettimeofday(&endTime, NULL);
runTime = (endTime.tv_sec * 1000 + endTime.tv_usec / 1000) - (startTime.tv_sec * 1000 + startTime.tv_usec / 1000);
printf(" of %d\t %.0lf\n", n, runTime);
fprintf(delp, "\n%d\t%.0lf", n, runTime);
}
fprintf(dotty, "}");
fclose(insp);
fclose(delp);
return 0;
}
For insDel.h code goto:
- Treap Insert and Delete Operations
Find the insert and delete operations for treap at this link.
For genOp.h code goto:
- Treap display
Display the treap data structure using dotty. Find its code here.
Treap - autoInsDel.c
#include
#include
#include"treap.insDel.h"
int count = 0;
// randomly generate n nodes for TREAP
TREAP genRandTreap(TREAP t, int n)
{
int i = 0;
TREAP temp;
srand((int)time(NULL));
for ( ; i < n; i++)
{
temp = (TREAP)malloc(sizeof (struct treap)); // allocate memory and initialize pointers
temp->llink = temp->rlink = temp->plink = NULL;
temp->info = rand()%1000; // put a random info and
temp->priority = rand()%10000; // a random priority
temp->count = ++count;
// printf("\nCreated: %d\t%d\n", temp->info, temp->priority);
t = insert(t, temp); // insert created node to the treap
}
return t;
}
// recursively deletes the root of the treap
TREAP autodelRoot(TREAP t, int m)
{
int i, check = 0;
TREAP temp = NULL;
for (i = 0; i < m; i++)
{
if (t == NULL)
printf("\tTree empty\t"); // if treap is empty
else
{
// printf("%d-%d deleted.\n", t->info, t->priority);
t = delete(t, t); // call to delete the root of the treap
// dispTree(t);
check++;
}
}
printf("\t%d nodes deleted", check); // gives the number of nodes deleted
return t;
}
#include
#include"treap.insDel.h"
int count = 0;
// randomly generate n nodes for TREAP
TREAP genRandTreap(TREAP t, int n)
{
int i = 0;
TREAP temp;
srand((int)time(NULL));
for ( ; i < n; i++)
{
temp = (TREAP)malloc(sizeof (struct treap)); // allocate memory and initialize pointers
temp->llink = temp->rlink = temp->plink = NULL;
temp->info = rand()%1000; // put a random info and
temp->priority = rand()%10000; // a random priority
temp->count = ++count;
// printf("\nCreated: %d\t%d\n", temp->info, temp->priority);
t = insert(t, temp); // insert created node to the treap
}
return t;
}
// recursively deletes the root of the treap
TREAP autodelRoot(TREAP t, int m)
{
int i, check = 0;
TREAP temp = NULL;
for (i = 0; i < m; i++)
{
if (t == NULL)
printf("\tTree empty\t"); // if treap is empty
else
{
// printf("%d-%d deleted.\n", t->info, t->priority);
t = delete(t, t); // call to delete the root of the treap
// dispTree(t);
check++;
}
}
printf("\t%d nodes deleted", check); // gives the number of nodes deleted
return t;
}
Treap - randomInsDel.c
#include
#include
#include"treap.insDel.h"
int countTraverse;
TREAP randomInsert(TREAP t)
{
int n, check = 0;
char c;
struct timeval start, end;
double runTime;
FILE *fp;
fp = fopen("r.dat", "w");
printf("\nEnter number of nodes to randomly generate Red-Black Tree: ");
scanf("%d", &n);
printf("\nDo you want existing tree to be updated by random insertion? Press 'y' to continue...");
scanf("%*c%c", &c);
if (c == 'y' || c == 'Y')
{
gettimeofday(&start, NULL);
t = genRandTREAP(t, n);
gettimeofday(&end, NULL);
}
else
{
printf("Do you want existing tree to be deleted? Press 'y' to continue...");
scanf("%*c%c", &c);
if (c == 'y' || c == 'Y')
{
t = NULL;
gettimeofday(&start, NULL);
t = genRandTREAP(t, n);
gettimeofday(&end, NULL);
}
else
{
check = 1;
printf("\nExisting tree retained.\n");
}
}
if (!check)
{
runTime = (end.tv_sec * 1000 + end.tv_usec / 1000) - (start.tv_sec * 1000 + start.tv_usec / 1000);
printf("\t%d\t%ld\n", n, runTime);
fprintf(fp, "%d\t%ld\n", n, runTime);
}
fclose(fp);
return t;
}
// traverse in preorder to find node at index 'n'
// a very costly algorithm!!!
TREAP nTraverse(TREAP t, int n)
{
int i;
TREAP temp = NULL;
if (t == NULL || n == 0) // return NULL if tree is NULL
return NULL;
countTraverse++;
if (countTraverse == n) // if node at index 'n' is found, return the node
{
// printf("countTraverse: %d, n: %d, Node: %d\n", countTraverse, n, t->info);
return t;
}
temp = nTraverse(t->llink, n); // recursively call with left children
if (temp == NULL) // only if there is no node at index at left subtree,
temp = nTraverse(t->rlink, n); // move to right subtree
return temp;
}
TREAP autodel(TREAP t, int m)
{
int i, n, check = 0;
TREAP temp = NULL;
srand((int)time(NULL));
// printf("\nEnter the number of nodes to auto delete: ");
// scanf("%d", &m);
for (i = 0; i < m; i++)
{
n = (rand() % (m - i)) + 1;
countTraverse = 0;
if ((temp = nTraverse(t, n)) == NULL)
printf("Node at index %d cannot be deleted!\n", n);
else
{
// printf("%d-%c deleted.\n", temp->info, temp->color);
t = rbDelete(t, temp);
// dispTree(t);
check++;
}
}
printf("\t%d nodes deleted", check);
return t;
}
#include
#include"treap.insDel.h"
int countTraverse;
TREAP randomInsert(TREAP t)
{
int n, check = 0;
char c;
struct timeval start, end;
double runTime;
FILE *fp;
fp = fopen("r.dat", "w");
printf("\nEnter number of nodes to randomly generate Red-Black Tree: ");
scanf("%d", &n);
printf("\nDo you want existing tree to be updated by random insertion? Press 'y' to continue...");
scanf("%*c%c", &c);
if (c == 'y' || c == 'Y')
{
gettimeofday(&start, NULL);
t = genRandTREAP(t, n);
gettimeofday(&end, NULL);
}
else
{
printf("Do you want existing tree to be deleted? Press 'y' to continue...");
scanf("%*c%c", &c);
if (c == 'y' || c == 'Y')
{
t = NULL;
gettimeofday(&start, NULL);
t = genRandTREAP(t, n);
gettimeofday(&end, NULL);
}
else
{
check = 1;
printf("\nExisting tree retained.\n");
}
}
if (!check)
{
runTime = (end.tv_sec * 1000 + end.tv_usec / 1000) - (start.tv_sec * 1000 + start.tv_usec / 1000);
printf("\t%d\t%ld\n", n, runTime);
fprintf(fp, "%d\t%ld\n", n, runTime);
}
fclose(fp);
return t;
}
// traverse in preorder to find node at index 'n'
// a very costly algorithm!!!
TREAP nTraverse(TREAP t, int n)
{
int i;
TREAP temp = NULL;
if (t == NULL || n == 0) // return NULL if tree is NULL
return NULL;
countTraverse++;
if (countTraverse == n) // if node at index 'n' is found, return the node
{
// printf("countTraverse: %d, n: %d, Node: %d\n", countTraverse, n, t->info);
return t;
}
temp = nTraverse(t->llink, n); // recursively call with left children
if (temp == NULL) // only if there is no node at index at left subtree,
temp = nTraverse(t->rlink, n); // move to right subtree
return temp;
}
TREAP autodel(TREAP t, int m)
{
int i, n, check = 0;
TREAP temp = NULL;
srand((int)time(NULL));
// printf("\nEnter the number of nodes to auto delete: ");
// scanf("%d", &m);
for (i = 0; i < m; i++)
{
n = (rand() % (m - i)) + 1;
countTraverse = 0;
if ((temp = nTraverse(t, n)) == NULL)
printf("Node at index %d cannot be deleted!\n", n);
else
{
// printf("%d-%c deleted.\n", temp->info, temp->color);
t = rbDelete(t, temp);
// dispTree(t);
check++;
}
}
printf("\t%d nodes deleted", check);
return t;
}
Treap tags
Mtreap.main treap.main.c /^int main(int argc, char **argv)$/autodel treap.randomInsDel.c /^TREAP autodel(TREAP t, int m)$/
autodelRoot treap.autoInsDel.c /^TREAP autodelRoot(TREAP t, int m)$/
delete treap.insDel.h /^TREAP delete(TREAP t, TREAP z) \/\/ z is node /
dispInDotty treap.genOp.h /^void dispInDotty(TREAP t, FILE *fp)$/
dispTree treap.genOp.h /^void dispTree(TREAP T)$/
genRandTreap treap.autoInsDel.c /^TREAP genRandTreap(TREAP t, int n)$/
getnode treap.genOp.h /^TREAP getnode()$/
insert treap.insDel.h /^TREAP insert(TREAP T, TREAP z)$/
insertFixUp treap.insDel.h /^TREAP insertFixUp(TREAP t, TREAP temp)$/
leftRotate treap.genOp.h /^TREAP leftRotate(TREAP T, TREAP x) $/
nTraverse treap.randomInsDel.c /^TREAP nTraverse(TREAP t, int n)$/
randomInsert treap.randomInsDel.c /^TREAP randomInsert(TREAP t)$/
rightRotate treap.genOp.h /^TREAP rightRotate(TREAP T, TREAP x) $/
search treap.genOp.h /^TREAP search(TREAP t, int key)$/
Check http://hubpages.com/hub/treap for a better and clean display of the same code.
Treap - insDel.h
#include#include
#include"treap.genOp.h"
// to fixup the tree after insertions
TREAP insertFixUp(TREAP t, TREAP temp)
{
while (temp != NULL && temp->plink != NULL && temp->priority < temp->plink->priority)
{
if (temp == temp->plink->llink) // if temp is left child of its parent
t = rightRotate(t, temp->plink); // right rotate at its parent to make temp as parent
else // if (temp = temp->plink->rlink) // so that priorities are satisfied as min heap
t = leftRotate(t, temp->plink); // else left rotate
} // to satisfy min heap property
return t;
}
// insert a new treap node with random info and random priority, a BST Insert
TREAP insert(TREAP T, TREAP z)
{
TREAP y = NULL, x = T;
if (T == NULL)
return z;
while (x != NULL) // insert at a suitable position, referenced with BST
{
y = x;
if (z->info < x->info)
x = x->llink;
else
x = x->rlink;
}
z->plink = y;
if (z->info < y->info)
y->llink = z;
else
y->rlink = z;
return insertFixUp(T, z);
}
// delete treap node only when it becomes a leaf node
TREAP delete(TREAP t, TREAP z) // z is node to be deleted
{
while (z->llink != NULL || z->rlink != NULL) // until z becomes leaf
{
if (z->rlink == NULL) // checking for non-rotation positions
t = rightRotate(t, z); // as there is no right rotation when there its right pointer is NULL
if (z->llink == NULL)
t = leftRotate(t, z);
if (z->plink != NULL && z == z->plink->llink) // if z is left child of its parent then right rotate at it
t = rightRotate(t, z);
else // else left rotate at it
t = leftRotate(t, z);
}
if (z->llink == NULL && z->rlink == NULL) // if z is leaf, then delete it
{
if (z->plink == NULL) // if z is the only root node, return NULL
return NULL;
else
{
if (z == z->plink->llink) // else delete it
z->plink->llink = NULL;
else
z->plink->rlink = NULL;
free(z);
}
}
return t;
}
#include
#include"treap.genOp.h"
// to fixup the tree after insertions
TREAP insertFixUp(TREAP t, TREAP temp)
{
while (temp != NULL && temp->plink != NULL && temp->priority < temp->plink->priority)
{
if (temp == temp->plink->llink) // if temp is left child of its parent
t = rightRotate(t, temp->plink); // right rotate at its parent to make temp as parent
else // if (temp = temp->plink->rlink) // so that priorities are satisfied as min heap
t = leftRotate(t, temp->plink); // else left rotate
} // to satisfy min heap property
return t;
}
// insert a new treap node with random info and random priority, a BST Insert
TREAP insert(TREAP T, TREAP z)
{
TREAP y = NULL, x = T;
if (T == NULL)
return z;
while (x != NULL) // insert at a suitable position, referenced with BST
{
y = x;
if (z->info < x->info)
x = x->llink;
else
x = x->rlink;
}
z->plink = y;
if (z->info < y->info)
y->llink = z;
else
y->rlink = z;
return insertFixUp(T, z);
}
// delete treap node only when it becomes a leaf node
TREAP delete(TREAP t, TREAP z) // z is node to be deleted
{
while (z->llink != NULL || z->rlink != NULL) // until z becomes leaf
{
if (z->rlink == NULL) // checking for non-rotation positions
t = rightRotate(t, z); // as there is no right rotation when there its right pointer is NULL
if (z->llink == NULL)
t = leftRotate(t, z);
if (z->plink != NULL && z == z->plink->llink) // if z is left child of its parent then right rotate at it
t = rightRotate(t, z);
else // else left rotate at it
t = leftRotate(t, z);
}
if (z->llink == NULL && z->rlink == NULL) // if z is leaf, then delete it
{
if (z->plink == NULL) // if z is the only root node, return NULL
return NULL;
else
{
if (z == z->plink->llink) // else delete it
z->plink->llink = NULL;
else
z->plink->rlink = NULL;
free(z);
}
}
return t;
}
No comments:
Post a Comment