Problem 4. (25 pts) Various Sorting Problems. (a) (10 pts) Propose an efficient

ID: 3603975 • Letter: P

Question

Problem 4. (25 pts) Various Sorting Problems. (a) (10 pts) Propose an efficient algorithm for the following problem. The input is composed of a heap A of size n, and an additional element a. The algorithm's objective is to return (say, print to the screen) all elements in A that are greater than or equal to x (note that x is not necessarily in A). The running time of your algorithm should be O(k) where k is the number of elements reported by the algorithm. Prove the correctness and runtime of the algorithm. (b) (15 pts) Given a BST T, let us add a field size that keeps track of the number of nodes in T 1. (2pt) How would you alter Insert) to update the size of the tree (and all its subtrees) when we 2. (3pt) How would you alter Delete) to update the size of the tree (and all its subtrees) when we 3. (10pt) Write a code (that uses the size field) for the quantile problem: given a BST T and a value add a new node to T, in a way that doesn't increase the runtime of Insert )? remove a node from T, in a way that doesn't increase the runtime of Delete()? v, Quantile(T, v) should return the number of elements in T which are

Explanation / Answer

// C program to demonstrate insert operation in binary search tree

#include<stdio.h>

#include<stdlib.h>

struct node

{

int key;

struct node *left, *right;

};

// A utility function to create a new BST node

struct node *newNode(int item)

{

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

}

// A utility function to do inorder traversal of BST

void inorder(struct node *root)

{

if (root != NULL)

{

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);

}

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key)

{

/* If the tree is empty, return a new node */

if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

}

// Driver Program to test above functions

int main()

{

/* Let us create following BST

30 70

/ /

20 40 60 80 */

struct node *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

// print inoder traversal of the BST

inorder(root);

return 0;

}