Scribd
Upload
6 views5 pages

Advanced Data Structures Assignment

The document presents an assignment on implementing a treap data structure using C programming. It includes code for creating nodes, merging, splitting, inserting, and deleting elements in the treap, along with an inorder traversal function. The main function demonstrates the insertion of keys and the deletion of a specific key, showcasing the treap's functionality.

Uploaded by

lalitha vaddadi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views5 pages

Advanced Data Structures Assignment

The document presents an assignment on implementing a treap data structure using C programming. It includes code for creating nodes, merging, splitting, inserting, and deleting elements in the treap, along with an inorder traversal function. The main function demonstrates the insertion of keys and the deletion of a specific key, showcasing the treap's functionality.

Uploaded by

lalitha vaddadi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

ADVANCED DATA STRUCTURES ASSIGNMENT

V Hari Priya Subramanya Lalitha


PhD Computer Science – 2023
SAU/CS(PE)/2023/03
Question 2: Implementing treap using C programming

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Node {
int key, priority;
struct Node *left, *right;
};

struct Node *createNode(int key) {


struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->key = key;
newNode->priority = rand(); // Random priority assignment
newNode->left = newNode->right = NULL;
return newNode;
}

struct Node *merge(struct Node *left, struct Node *right) {


if (left == NULL)
return right;
if (right == NULL)
return left;

if (left->priority > right->priority) {


left->right = merge(left->right, right);
return left;
} else {
right->left = merge(left, right->left);
return right;
}
}

void split(struct Node *root, int key, struct Node **left, struct Node **right) {
if (root == NULL) {
*left = *right = NULL;
return;
}

if (root->key <= key) {


*left = root;
split(root->right, key, &((*left)->right), right);
} else {
*right = root;
split(root->left, key, left, &((*right)->left));
}
}

void insert(struct Node **root, int key) {


struct Node *newNode = createNode(key);
struct Node *left, *right;

split(*root, key, &left, &right);


*root = merge(merge(left, newNode), right);
}

void erase(struct Node **root, int key) {


if (*root == NULL) return;
if ((*root)->key == key) {
struct Node *temp = *root;
*root = merge((*root)->left, (*root)->right);
free(temp);
} else if (key < (*root)->key) {
erase(&((*root)->left), key);
} else {
erase(&((*root)->right), key);
}
}

void inorderTraversal(struct Node *root) {


if (root) {
inorderTraversal(root->left);
printf("%d ", root->key);
inorderTraversal(root->right);
}
}

int main() {
srand(time(NULL));

struct Node *root = NULL;

int keys[] = {5, 2, 8, 1, 3, 7, 9};


int numKeys = sizeof(keys) / sizeof(keys[0]);

for (int i = 0; i < numKeys; ++i) {


insert(&root, keys[i]);
}

printf("Inorder traversal of the Treap: ");


inorderTraversal(root);
printf("\n");

erase(&root, 3); // Delete element 3


printf("Inorder traversal after deleting 3: ");
inorderTraversal(root);
printf("\n");

return 0;
}

You might also like