Simplify the code as far as possible in C so that it only contains the elements required that are listed below:

Define a new type, node_t, which represents a struct containing

everything needed for the node of a binary search tree.

Implement an int search(node_t * node, int toFind)

function which returns 1 if the variable toFind exists in the tree, and

0 otherwise,

Implement a node_t * createTree(int firstElem) func[1]tion which allocates a new Tree and returns a pointer to its root,

Implement a void destroyTree(node_t * node) function

which takes a trees root and deallocates the entire tree.

Implement a void insert(node_t * node, int elem)

function which inserts elem at the appropriate place in the tree.

Implement a void delete(node_t * node, int elem)

function which finds and deletes elem from the tree.

CODE:

#include #include #include #include

typedef struct _node { int elem; struct _node * parent; struct _node * left; struct _node * right; pthread_mutex_t *mutex;

} node_t;

int search(node_t * node, int toFind) { node_t* current=node; pthread_mutex_lock(node->mutex); //lock current node // if element is greater release current and lock left else lock right //when node is passed over release lock while (current->elem!=toFind) { if(current!=NULL) { pthread_mutex_unlock(node->mutex); pthread_mutex_lock(node->left->mutex); if(current->elem>toFind) { current=current->left; pthread_mutex_unlock(node->left->mutex);

} else{ pthread_mutex_lock(node->right->mutex); current=current->right; pthread_mutex_unlock(node->right->mutex); } } if(current==NULL) { return 0; } } return current->elem; // signals to main() that this is unimplemented }

node_t * createTree(int firstElem) { node_t *root=malloc(sizeof(node_t)); root->parent=NULL; root->right=NULL; root->left=NULL; root->elem=firstElem;

//for synchornization pthread_mutex_t* mutex = malloc(sizeof(pthread_mutex_t)); pthread_mutex_init(mutex,NULL); root->mutex=mutex;

return root; // signals to main() that this is unimplemented }

void destroyTree(node_t * node) { if(node==NULL) { return; } destroyTree(node->left); destroyTree(node->right); free(node); }

void insert(node_t * node, int newElem) {

//lock as soon enter insert //lock the current node and keep on locking recursively till NULL is found then release all nodes //after insetion is done in a recursive way //allocate new node and it's lock pthread_mutex_lock(node->mutex); if (node->elem == newElem) { pthread_mutex_unlock(node->mutex); return ; }

if (newElem < node->elem) { if (node->left != NULL) { insert(node->left, newElem); pthread_mutex_unlock(node->mutex); } else { node_t * newNode = malloc(sizeof(node_t)); newNode->left = NULL; newNode->right = NULL; newNode->parent = node; newNode->elem = newElem; node->left = newNode; pthread_mutex_t *mutex=malloc(sizeof(pthread_mutex_t)); pthread_mutex_init(mutex,NULL); newNode->mutex=mutex; pthread_mutex_unlock(node->mutex); return ; // we're done! } } else { if (node->right != NULL) { insert(node->right, newElem); pthread_mutex_unlock(node->mutex); } else { // can't go right; allocate a new node node_t * newNode = malloc(sizeof(node_t)); newNode->left = NULL; newNode->right = NULL; newNode->parent = node; newNode->elem = newElem; node->right = newNode; pthread_mutex_t *mutex=malloc(sizeof(pthread_mutex_t)); pthread_mutex_init(mutex,NULL); newNode->mutex=mutex; pthread_mutex_unlock(node->mutex); return ; // we're done! } } }

node_t * getMax(node_t * node) { // The maximum value under `node` is its rightmost child pthread_mutex_lock(node->right->mutex); node_t * curr = node; while (curr->right != NULL) { curr = curr->right; } return curr; pthread_mutex_unlock(node->right->mutex); }

node_t * getMin(node_t * node) { // The minimum value under `node` is its leftmost child pthread_mutex_lock(node->left->mutex); node_t * curr = node; while (curr->left != NULL) { curr = curr->left; } pthread_mutex_unlock(node->left->mutex); return curr; }

int delete(node_t * node, int toDelete) { // Deletes a node. // returns: true if node deleted // false if couldn't delete (didn't exist or was root)

// go left if smaller //lock as soon enter delete //lock the current node and keep on locking recursively till NULL is found then release all nodes //after deletion is done in a recursive way //acquire lock on respective deletion of node // for left node deletion lock left node // for right node deletion lock right node pthread_mutex_lock(node->mutex); if (toDelete < node->elem) {

if (node->left != NULL) { pthread_mutex_unlock(node->mutex); return delete(node->left, toDelete); } else{ pthread_mutex_unlock(node->mutex); return false; }

// go right if bigger } else if (toDelete > node->elem) { if (node->right != NULL) { pthread_mutex_unlock(node->mutex); return delete(node->right, toDelete); } else { pthread_mutex_unlock(node->mutex); return false; }

// Not >, not <, so we found what we want to delete! } else {

if (node->parent == NULL) { pthread_mutex_unlock(node->mutex); return false; // don't remove root } // Save these; we'll need them later. node_t * parent = node->parent; bool leftChild = (node->parent->left == node);

// if it has no children, simply remove. if (node->left == NULL && node->right == NULL) {

if (leftChild) { parent->left = NULL; } else { parent->right = NULL; } pthread_mutex_unlock(node->mutex); free(node); return true; } // If it has only a left child, which shifts into its place. else if (node->left != NULL && node->right == NULL) { pthread_mutex_lock(node->left->mutex); node->left->parent = node->parent; if (leftChild) { parent->left = node->left; } else { parent->right = node->left; } pthread_mutex_unlock(node->left->mutex); free(node); return true; } // if it only has a right child, which shifts into its place. else if (node->left == NULL && node->right != NULL) { pthread_mutex_lock(node->right->mutex); node->right->parent = node->parent; if (leftChild) { parent->left = node->right; } else { parent->right = node->right; } pthread_mutex_unlock(node->right->mutex); free(node); return true; } // It has two children. // Pick the smallest item in the rightmost subtree, // ...then replace `node` with it, // ...then delete that largest node in the rightmost subtree. else { node_t * successor = getMin(node->right); node->elem = successor->elem; return delete(successor, successor->elem); } } }

void inorderPrintTree(node_t * node) { if (node->left != NULL) { inorderPrintTree(node->left); } printf("%d ", node->elem); if (node->right != NULL) { inorderPrintTree(node->right); } }

void preorderPrintTree(node_t * node) { printf("%d ", node->elem); if (node->left != NULL) { preorderPrintTree(node->left); } if (node->right != NULL) { preorderPrintTree(node->right); } }

void printConnections(node_t * node) { if (node->left) {printConnections(node->left);} if (node->right) {printConnections(node->right);}

if (node->left) {printf("%d->", node->left->elem);} printf("%d", node->elem); if (node->right) {printf("<-%d", node->right->elem);} printf(" "); } node_t *root;

void *insertThread(void *i) { int a = *((int *) i); printf("%d",a); insert(root,a); }

void *deleteThread(void *i) { int a = *((int *) i); printf("%d",a); delete(root,a);

}