Task2: complete all of the uncompleted functions in Fli

Question

Task2: complete all of the uncompleted functions in FlightDb.c

Chinni Guna Venkata Prasanth · Accepted Answer

// Implementation of the Tree ADT #include #include #include #include #include #include "List.h" #include "Record.h" #include "Tree.h" typedef struct node *Node; struct node { Record rec; Node left; Node right; int height; Node parent; // IMPORTANT: Do not modify the fields above // You may add additional fields below if necessary }; typedef struct tree *Tree; struct tree { Node root; int (*compare)(Record, Record); // IMPORTANT: Do not modify the fields above // You may add additional fields below if necessary }; // structure to store the return values of insert function typedef struct insertReturn *InsertReturn; struct insertReturn { Node root; bool result; }; static void doTreeFree(Node n, bool freeRecords); //////////////////////////////////////////////////////////////////////// // Provided functions // !!! DO NOT MODIFY THESE FUNCTIONS !!! Tree TreeNew(int (*compare)(Record, Record)) { Tree t = malloc(sizeof(*t)); if (t == NULL) { fprintf(stderr, "error: out of memory "); exit(EXIT_FAILURE); } t->root = NULL; t->compare = compare; return t; } void TreeFree(Tree t, bool freeRecords) { doTreeFree(t->root, freeRecords); free(t); } static void doTreeFree(Node n, bool freeRecords) { if (n != NULL) { doTreeFree(n->left, freeRecords); doTreeFree(n->right, freeRecords); if (freeRecords) { RecordFree(n->rec); } free(n); } } //////////////////////////////////////////////////////////////////////// //helper functions //to find max(a,b) static int max(int a, int b) { return (a > b)? a : b; } //to return the hight of a node in the avl tree static int height(Node N) { if (N == NULL) return 0; return N->height; } //to create a new node in the avl tree static Node newNode(Record r) { Node newNode = (Node) malloc (sizeof(struct node)); newNode->rec = r; newNode->left = NULL; newNode->right = NULL; newNode->parent = NULL; newNode->height = 1; return(newNode); } //to do right rotation static Node rightRotate(Node y) { Node p = y->parent; Node x = y->left; Node T2 = x->right; // Perform rotation x->parent = p; x->right = y; y->parent = x; y->left = T2; if(T2 != NULL) { T2->parent = y; } // Update heights y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; // Return new root return x; } //to do left rotation static Node leftRotate(Node x) { Node p = x->parent; Node y = x->right; Node T2 = y->left; // Perform rotation y->parent = p; y->left = x; x->parent = y; x->right = T2; if(T2 != NULL) { T2->parent = x; } // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; // Return new root return y; } // to return the balance factor of a node in the avl tree static int getBalance(Node N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } //to compare two records static int compareRecord(Record R1, Record R2) { int x = strcmp(RecordGetFlightNumber(R1), RecordGetFlightNumber(R2)); if(x != 0) { return x; } int d = RecordGetDepartureDay(R1) - RecordGetDepartureDay(R2); if(d != 0) { return d; } int h = RecordGetDepartureHour(R1) - RecordGetDepartureHour(R1); if(h != 0) { return h; } int m = RecordGetDepartureMinute(R1) - RecordGetDepartureMinute(R2); if(m != 0) { return m; } return 0; } //to insert a new node into the avl tree static InsertReturn insert(Node node, Record key, Tree t) { InsertReturn ret = (InsertReturn) malloc(sizeof(struct insertReturn)); //Perform the normal BST insertion if (node == NULL) { ret->root = newNode(key); ret->result = true; return ret; } //check whether the node is same or not if(compareRecord(key, node->rec) == 0) { ret->root = node; ret->result = false; return ret; } if (t->compare(key, node->rec) < 0) { InsertReturn temp1 = insert(node->left, key, t); node->left = temp1->root; temp1->root->parent = node; } else { InsertReturn temp2 = insert(node->right, key, t); node->right = temp2->root; temp2->root->parent = node; } // Update height of this ancestor node node->height = 1 + max(height(node->left), height(node->right)); //Get the balance factor of this ancestor node to check whether this node became unbalanced int balance = getBalance(node); // If this node becomes unbalanced, then there are 4 cases // Left Left Case if (balance > 1 && t->compare(key, node->left->rec) < 0) { ret->root = rightRotate(node); ret->result = true; return ret; } // Right Right Case if (balance < -1 && t->compare(key, node->right->rec) >= 0) { ret->root = leftRotate(node); ret->result = true; return ret; } // Left Right Case if (balance > 1 && t->compare(key, node->left->rec) >= 0) { node->left = leftRotate(node->left); ret->root = rightRotate(node); ret->result = true; return ret; } // Right Left Case if (balance < -1 && t->compare(key, node->right->rec) < 0) { node->right = rightRotate(node->right); ret->root = leftRotate(node); ret->result = true; return ret; } // return the (unchanged) node pointer ret->root = node; ret->result = true; return ret; } // to search in the avl tree static Node search(Node root, Record key, Tree t) { // Base Cases: root is null or key is present at root if (root == NULL || t->compare(root->rec, key) == 0) { return root; } // Key is greater than root's key if (t->compare(root->rec, key) < 0) { return search(root->right, key, t); } // Key is smaller than root's key return search(root->left, key, t); } //to find minimum in a subtree rooted at node static Node minValue(Node node) { Node current = node; // loop down to find the leftmost leaf while (current->left != NULL) { current = current->left; } return current; } // to find the inorder successor of a node in the avl tree static Node inOrderSuccessor(Node root, Node n) { if (n->right != NULL) return minValue(n->right); struct node* p = n->parent; while (p != NULL && n == p->right) { n = p; p = p->parent; } return p; } //////////////////////////////////////////////////////////////////////// // Functions you need to implement bool TreeInsert(Tree t, Record rec) { InsertReturn ret = insert(t->root, rec, t); t->root = ret->root; return ret->result; } Record TreeSearch(Tree t, Record rec) { Node ret = search(t->root, rec, t); return ret->rec; } List TreeSearchBetween(Tree t, Record lower, Record upper) { List l = ListNew(); Node first = search(t->root, lower, t); ListAppend(l, first->rec); while(1) { Node s = inOrderSuccessor(t->root, first); ListAppend(l, s->rec); if(t->compare(s->rec, upper) == 0 || s == NULL) { break; } } return l; } Record TreeNext(Tree t, Record rec) { Node r = search(t->root, rec, t); if(r == NULL) { return NULL; } Node ret = inOrderSuccessor(t->root, r); if(ret != NULL) { return ret->rec; } return NULL; } ////////////////////////////////////////////////////////////////////////

Task2: complete all of the uncompleted functions in FlightDb.c

Get Instant Homework HelpOn Your Mobile

Get Instant Homework HelpOn Your Mobile