Spaces:
Sleeping
Sleeping
| // Treap (Tree + Heap) - randomized binary search tree | |
| // BST by key, heap by priority - provides balanced tree with high probability | |
| typedef struct TreapNode { | |
| int key; | |
| int priority; | |
| struct TreapNode *left; | |
| struct TreapNode *right; | |
| } TreapNode; | |
| unsigned int rand_seed = 42; | |
| int my_rand() { | |
| rand_seed = rand_seed * 1103515245 + 12345; | |
| return (rand_seed >> 16) & 0x7FFF; | |
| } | |
| TreapNode* create_node(int key) { | |
| TreapNode *node = (TreapNode*)malloc(sizeof(TreapNode)); | |
| node->key = key; | |
| node->priority = my_rand(); | |
| node->left = NULL; | |
| node->right = NULL; | |
| return node; | |
| } | |
| TreapNode* rotate_right(TreapNode *root) { | |
| TreapNode *new_root = root->left; | |
| root->left = new_root->right; | |
| new_root->right = root; | |
| return new_root; | |
| } | |
| TreapNode* rotate_left(TreapNode *root) { | |
| TreapNode *new_root = root->right; | |
| root->right = new_root->left; | |
| new_root->left = root; | |
| return new_root; | |
| } | |
| TreapNode* insert(TreapNode *root, int key) { | |
| if (!root) { | |
| return create_node(key); | |
| } | |
| if (key < root->key) { | |
| root->left = insert(root->left, key); | |
| // Maintain heap property | |
| if (root->left->priority > root->priority) { | |
| root = rotate_right(root); | |
| } | |
| } else if (key > root->key) { | |
| root->right = insert(root->right, key); | |
| // Maintain heap property | |
| if (root->right->priority > root->priority) { | |
| root = rotate_left(root); | |
| } | |
| } | |
| return root; | |
| } | |
| TreapNode* delete_node(TreapNode *root, int key) { | |
| if (!root) return NULL; | |
| if (key < root->key) { | |
| root->left = delete_node(root->left, key); | |
| } else if (key > root->key) { | |
| root->right = delete_node(root->right, key); | |
| } else { | |
| // Found the node to delete | |
| if (!root->left && !root->right) { | |
| free(root); | |
| return NULL; | |
| } else if (!root->left) { | |
| TreapNode *temp = root->right; | |
| free(root); | |
| return temp; | |
| } else if (!root->right) { | |
| TreapNode *temp = root->left; | |
| free(root); | |
| return temp; | |
| } else { | |
| // Both children exist - rotate based on priority | |
| if (root->left->priority > root->right->priority) { | |
| root = rotate_right(root); | |
| root->right = delete_node(root->right, key); | |
| } else { | |
| root = rotate_left(root); | |
| root->left = delete_node(root->left, key); | |
| } | |
| } | |
| } | |
| return root; | |
| } | |
| TreapNode* search(TreapNode *root, int key) { | |
| if (!root || root->key == key) { | |
| return root; | |
| } | |
| if (key < root->key) { | |
| return search(root->left, key); | |
| } else { | |
| return search(root->right, key); | |
| } | |
| } | |
| int get_height(TreapNode *root) { | |
| if (!root) return 0; | |
| int left_height = get_height(root->left); | |
| int right_height = get_height(root->right); | |
| return 1 + (left_height > right_height ? left_height : right_height); | |
| } | |
| void free_treap(TreapNode *root) { | |
| if (!root) return; | |
| free_treap(root->left); | |
| free_treap(root->right); | |
| free(root); | |
| } | |
| int main() { | |
| TreapNode *root = NULL; | |
| clock_t start = clock(); | |
| // Insert operations | |
| for (int i = 0; i < NUM_OPERATIONS; i++) { | |
| root = insert(root, my_rand() % 50000); | |
| } | |
| // Search operations | |
| int found = 0; | |
| for (int i = 0; i < NUM_OPERATIONS / 2; i++) { | |
| if (search(root, my_rand() % 50000)) { | |
| found++; | |
| } | |
| } | |
| int height = get_height(root); | |
| // Delete operations | |
| for (int i = 0; i < NUM_OPERATIONS / 3; i++) { | |
| root = delete_node(root, my_rand() % 50000); | |
| } | |
| clock_t end = clock(); | |
| double time_spent = (double)(end - start) / CLOCKS_PER_SEC; | |
| printf("Treap: %d operations, %.6f seconds\n", NUM_OPERATIONS, time_spent); | |
| printf("Tree height: %d, Found: %d\n", height, found); | |
| free_treap(root); | |
| return 0; | |
| } | |