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 node’s key.
• The right sub tree of a node contains only nodes with keys greater than the node’s 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 node’s 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)

Traversal Type	In order	Preorder	Post order
Short Cut	L N R	N L R	L R N

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 < (*node)->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 < (*node)->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 < node->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(“u’ve entered wrong optionn”);

break;

}

}

return 0;

}

[mca@linuxlab1-58 ~]$vi t.c

[mca@linuxlab1-58 ~]$gcc t.c

[mca@linuxlab1-58 ~]$./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[mca@linuxlab1-57 ~]$

COMPLEXITY OF BINARY SEARCH TREE

It could be O(n^2) even if the tree is balanced.

Suppose you’re 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, you’ll have to traverse ~i nodes, which yields O(n^2).

In general, if you’d like to keep the insertion and retrieval at O(nlogn), you need to use Self Balancing trees