Data Structure

#include <stdlib.h> #include <stdio.h> #include <assert.h> // all the basic data structures and functions are included in this template // you can add your own auxiliary functions as you like // data type for avl tree nodes typedef struct AVLTreeNode { int key; //key of this item int value; //value (int) of this item int height; //height of the subtree rooted at this node struct AVLTreeNode *parent; //pointer to parent struct AVLTreeNode *left; //pointer to left child struct AVLTreeNode *right; //pointer to right child } AVLTreeNode; //data type for AVL trees typedef struct AVLTree{ int size; // count of items in avl tree AVLTreeNode *root; // root } AVLTree; // create a new AVLTreeNode AVLTreeNode *newAVLTreeNode(int k, int v ) { AVLTreeNode *new; new = malloc(sizeof(AVLTreeNode)); assert(new != NULL); new->key = k; new->value = v; new->height = 0; // height of this new node is set to 0 new->left = NULL; // this node has no child new->right = NULL; new->parent = NULL; // no parent return new; } // create a new empty avl tree AVLTree *newAVLTree() { AVLTree *T; T = malloc(sizeof (AVLTree)); assert (T != NULL); T->size = 0; T->root = NULL; return T; } // put your time complexity analysis of CreateAVLTree() here AVLTree *CreateAVLTree(const char *filename) { // put your code here } // put your time complexity analysis for CloneAVLTree() here AVLTree *CloneAVLTree(AVLTree *T) { // put your code here } // put your time complexity for ALVTreesUNion() here AVLTree *AVLTreesUnion(AVLTree *T1, AVLTree *T2) { //put your code here } // put your time complexity for ALVTreesIntersection() here AVLTree *AVLTreesIntersection(AVLTree *T1, AVLTree *T2) { //put your code here } // put the time complexity analysis for InsertNode() here int InsertNode(AVLTree *T, int k, int v) { //put your code here } // put your time complexity for DeleteNode() here int DeleteNode(AVLTree *T, int k, int v) { // put your code here } // put your time complexity analysis for Search() here AVLTreeNode *Search(AVLTree *T, int k, int v) { // put your code here } // put your time complexity analysis for freeAVLTree() here void FreeAVLTree(AVLTree *T) { // put your code here } // put your time complexity analysis for PrintAVLTree() here void PrintAVLTree(AVLTree *T) { // put your code here } int main() //sample main for testing { int i,j; AVLTree *tree1, *tree2, *tree3, *tree4, *tree5, *tree6, *tree7, *tree8; AVLTreeNode *node1; tree1=CreateAVLTree("stdin"); PrintAVLTree(tree1); FreeAVLTree(tree1); //you need to create the text file file1.txt // to store a set of items without duplicate items tree2=CreateAVLTree("file1.txt"); PrintAVLTree(tree2); tree3=CloneAVLTree(tree2); PrintAVLTree(tree3); FreeAVLTree(tree2); FreeAVLTree(tree3); //Create tree4 tree4=newAVLTree(); j=InsertNode(tree4, 10, 10); for (i=0; i<15; i++) { j=InsertNode(tree4, i, i); if (j==0) printf("(%d, %d) already exists\n", i, i); } PrintAVLTree(tree4); node1=Search(tree4,20,20); if (node1!=NULL) printf("key= %d value= %d\n",node1->key,node1->value); else printf("Key 20 does not exist\n"); for (i=17; i>0; i--) { j=DeleteNode(tree4, i, i); if (j==0) printf("Key %d does not exist\n",i); PrintAVLTree(tree4); } FreeAVLTree(tree4); //Create tree5 tree5=newAVLTree(); j=InsertNode(tree5, 6, 25); j=InsertNode(tree5, 6, 10); j=InsertNode(tree5, 6, 12); j=InsertNode(tree5, 6, 20); j=InsertNode(tree5, 9, 25); j=InsertNode(tree5, 10, 25); PrintAVLTree(tree5); //Create tree6 tree6=newAVLTree(); j=InsertNode(tree6, 6, 25); j=InsertNode(tree6, 5, 10); j=InsertNode(tree6, 6, 12); j=InsertNode(tree6, 6, 20); j=InsertNode(tree6, 8, 35); j=InsertNode(tree6, 10, 25); PrintAVLTree(tree6); tree7=AVLTreesIntersection(tree5, tree6); tree8=AVLTreesUnion(tree5,tree6); PrintAVLTree(tree7); PrintAVLTree(tree8); return 0; }