Research Assignment on Data File Structure

Research Assignment on Data File Structure Raghavendra Tyagi TOPIC OF ASSIGNMENT The letters in English language, make up words. While no word is less or more than another, one could view a word that appears before another in the dictionary is less than that word, and a word that appears afterwards is more. By this definition, identical words are the same. Parsing a file is when you read a file to collect information from the file. In this assignment, you will parse a file, and put all of the words in a Binary Search Tree. You will use the Binary Search Tree to collect data about the number of times a word was found in the file. The first word you encounter will be the root. If the next word is greater, put it to the right. If it is less, put it to the left. It is possible that the tree you make will be very sparse. Assume all words in the file are lower case or covert them to lower case. After you have loaded the file into your Binary Search Tree, the program should display the in-order, pre-order post-order traversal of the Binary Search Tree. The user should be given the chance to type a word. The computer should say the number of times the word was found in the file (zero or more). BINARY SEARCH TREE INTRODUCTION: In  computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a  node-based  binary tree  data structure which has the following properties The left  sub tree  of a node contains only nodes with keys less than the nodes key. The right sub tree of a node contains only nodes with keys greater than the nodes key. The left and right sub tree each must also be a binary search tree. There must be no duplicate nodes ADVANTAGE: The major advantage of binary search trees over other  data structures  is that the related sorting Algorithm and  search algorithms  such as  in-order traversal  can be very efficient. BINARY SEARCH TREE (PROPERTY): Letxbe a node in a binary search tree. Ifyis a node in the left sub tree ofx, theny. key x. key. OPERATIONS: Operations, such asfind, on a binary search tree require comparisons between nodes. These comparisons are made with calls to a comparator, which is a  subroutine  that computes the total order (linear order) on any two keys. This comparator can be explicitly or implicitly defined, depending on the language in which the binary search tree was implemented. SEARCHING: Searching a binary search tree for a specific key can be a  recursive  or an  iterative  process. We begin by examining the  root node. If the tree isnull, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left sub tree. Similarly, if the key is greater than that of the root, we search the right sub tree. This process is repeated until the key is found or the remaining sub tree is null. If the searched key is not found before a null sub tree is reached, then the item must not be present in the tree. INSERTION: Insertion begins as a search would begin; if the key is not equal to that of the root, we search the left or right sub trees as before. Eventually, we will reach an external node and add the new key-value pair (here encoded as a record new Node) as its right or left child, depending on the nodes key. In other words, we examine the root and recursively insert the new node to the left sub tree if its key is less than that of the root, or the right sub tree if its key is greater than or equal to the root. DELETION: There are three possible cases to consider: Deleting a leaf (node with no children):Deleting a leaf is easy, as we can simply remove it from the tree. Deleting a node with one child:Remove the node and replace it with its child. Deleting a node with two children:Call the node to be deletedN. Do not deleteN. Instead, choose either its  in-order  successor node or its in-order predecessor node,R. Replace the value ofNwith the value ofR, then deleteR. BST FIGURE: Preorder traversal sequence: F, B, A, D, C, E, G, I, H (Root, left, right) In order traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right) Post order traversal sequence: A, C, E, D, B, H, I, G, (left, right, root) ASSIGNMENT CODE #include #include struct treeNode { char data[10]; struct treeNode *left, *right; }; struct treeNode *root = NULL; struct treeNode* createNode(char data) { struct treeNode *newNode; newNode = (struct treeNode*)malloc(sizeof(struct treeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return(newNode); } void insertion(struct treeNode **node, char data) { if (*node == NULL) { *node = createNode(data); } else if (data data) { insertion((*node)->left, data); } else if (data > (*node)->data) { insertion((*node)->right, data); } } void deletion(struct treeNode **node, struct treeNode **parent, char data) { struct treeNode *tmpNode, *tmpParent; if (*node == NULL) return; if ((*node)->data == data) { if (!(*node)->left !(*node)->right) { if (parent) { if ((*parent)->left == *node) (*parent)->left = NULL; else (*parent)->right = NULL; free(*node); } else { free(*node); } } else if (!(*node)->right (*node)->left) { tmpNode = *node; (*parent)->right = (*node)->left; free(tmpNode); *node = (*parent)->right; } else if ((*node)->right !(*node)->left) { tmpNode = *node; (*parent)->left = (*node)->right; free(tmpNode); (*node) = (*parent)->left; } else if (!(*node)->right->left) { tmpNode = *node; (*node)->right->left = (*node)->left; (*parent)->left = (*node)->right; free(tmpNode); *node = (*parent)->left; } else { tmpNode = (*node)->right; while (tmpNode->left) { tmpParent = tmpNode; tmpNode = tmpNode->left; } tmpParent->left = tmpNode->right; tmpNode->left = (*node)->left; tmpNode->right =(*node)->right; free(*node); *node = tmpNode; } } else if (data data) { deletion((*node)->left, node, data); } else if (data > (*node)->data) { deletion((*node)->right, node, data); } } void findElement(struct treeNode *node, chardata) { if (!node) return; else if (data data) { findElement(node->left, data); } else if (data > node->data) { findElement(node->right, data); } else printf(data found: %sn, node->data); return; } void traverse(struct treeNode *node) { if (node != NULL) { traverse(node->left); printf(%3d, node->data); traverse(node->right); } return; } int main() { char data; int ch; while (1) { printf(1. Insertion in Binary Search Treen); printf(2. Deletion in Binary Search Treen); printf(3. Search Element in Binary Search Treen); printf(4. Inorder traversaln5. Exitn); printf(Enter your choice:); scanf(%d, ch); switch (ch) { case 1: while (1) { printf(Enter your data:); scanf(%s, data); insertion(root, data); printf(Continue Insertion(0/1):); scanf(%d, ch); if (!ch) break; } break; case 2: printf(Enter your data:); scanf(%s, data); deletion(root, NULL, data); break; case 3: printf(Enter value for data:); scanf(%s, data); findElement(root, data); break; case 4: printf(Inorder Traversal:n); traverse(root); printf(n); break; case 5: exit(0); default: printf(uve entered wrong optionn); break; } } return 0; } [[emailprotected] ~]$vi t.c [[emailprotected] ~]$gcc t.c [[emailprotected] ~]$./a.out OUTPUT: 1. Insertion in Binary Search Tree 2. Deletion in Binary Search Tree 3. Search Element in Binary Search Tree 4. Inorder traversal 5. Exit Enter your choice:1 Enter your data: aim Continue Insertion(0/1):1 Enter your data: age Continue Insertion(0/1):1 Enter your data: admit Continue Insertion(0/1):1 Enter your data: agree Continue Insertion(0/1):1 Enter your data: blue Continue Insertion(0/1):0 Resultant Binary Search Tree after insertion operation: aim / age blue / admit agree 1. Insertion in Binary Search Tree 2. Deletion in Binary Search Tree 3. Search Element in Binary Search Tree 4. Inorder traversal 5. Exit Enter your choice:4 Inorder Traversal: admit, age, agree, aim , blue 1. Insertion in Binary Search Tree 2. Deletion in Binary Search Tree 3. Search Element in Binary Search Tree 4. Inorder traversal 5. Exit Enter your choice:2 Enter your data:admit Delete node admit aim / age blue / agree 1. Insertion in Binary Search Tree 2. Deletion in Binary Search Tree 3. Search Element in Binary Search Tree 4. Inorder traversal 5. Exit Enter your choice:3 Enter value for data:age data found: age No of occurrence:1 1. Insertion in Binary Search Tree 2. Deletion in Binary Search Tree 3. Search Element in Binary Search Tree 4. Inorder traversa 5. Exit Enter your choice:5[[emailprotected] ~]$ COMPLEXITY OF BINARY SEARCH TREE It could be O(n^2) even if the tree is balanced. Suppose youre adding a sorted list of numbers, all larger than the largest number in the tree. In that case, all numbers will be added to the right child of the rightmost leaf in the tree, Hence O(n^2). For example, suppose that you add the numbers [15..115] to the following tree: The numbers will be added as a long chain, each node having a single right hand child. For the i-th element of the list, youll have to traverse ~i nodes, which yields O(n^2). In general, if youd like to keep the insertion and retrieval at O(nlogn), you need to use  Self Balancing trees