C programming assignment
examples/invalidtree0.b examples/invalidtree0.txt -5 1 -4 1 -3 1 -2 1 -1 1 0 1 1 1 2 1 5 1 4 0 examples/invalidtree1.b �ϼ�＃ﯿ�ý�Ȁ�̀�������Ԁ�Ą�� examples/invalidtree1.txt -2 3 -4 3 -5 0 -3 0 2 3 0 3 -1 0 1 0 5 1 4 0 examples/invalidtree2.b examples/invalidtree2.txt -5 1 -4 1 -3 1 -2 1 -1 1 0 1 1 1 3 1 4 0 examples/ops0.b examples/ops0.txt -5 i -4 i -3 i -2 i -1 i 0 i 1 i 2 i 3 i 4 i examples/ops1.b examples/ops1.txt -5 i -4 i -3 i -2 i -1 i 0 i 1 i 2 i 3 i 4 i 2 d examples/ops2.b examples/ops2.txt -5 i -4 i -3 i -2 i -1 i 2 d 0 i 1 i 2 i 3 i 4 i examples/ops3.b examples/ops3.txt 3 i 3 i 3 i 3 i 1 i 1 i 1 i 1 i 2 i 2 i 2 i 2 i 4 i 4 i 4 i 4 i 4 i 4 i 4 i 4 i 0 i 0 i 0 i 0 i 1 i 0 d 1 d 2 d 1 d 1 d examples/tree0.b �ϼ�＃ﯿ�ý�Ȁ�̀�������̀�Ą�� examples/tree0.txt -2 3 -4 3 -5 0 -3 0 2 3 0 3 -1 0 1 0 3 1 4 0 examples/tree1.b �ϼ�＃ﯿ�ý�Ā�̀�������Ѐ�� examples/tree1.txt -2 3 -4 3 -5 0 -3 0 1 3 0 2 -1 0 3 1 4 0 examples/tree2.b �ϼ�＃ﯿ�ý�Ȁ�̀�������̀�Ą�� examples/tree2.txt -2 3 -4 3 -5 0 -3 0 2 3 0 3 -1 0 1 0 3 1 4 0 examples/tree3.b examples/tree3.txt 2 3 0 3 0 2 0 0 1 3 1 0 2 0 4 3 3 3 3 3 2 0 3 0 4 3 3 0 4 0 4 3 4 0 4 3 4 0 4 0 #ifndef __HBT_TREE__ #define __HBT_TREE__ typedef struct _Tnode { int key; int height; struct _Tnode *left; struct _Tnode *right; } Tnode; #endif ECE36800 Programming Assignment 2 You are required to implement a program to construct a height-balanced binary search tree (BST), start- ing from an empty tree, based on a sequence of insertion and deletion operations. You may have to perform rotation(s) to maintain the height-balanceness of the tree after each insertion or deletion. Note that height- balanceness is defined as we covered in the class. Given a node, its balance is the height of its left subtree minus the height of its right subtree. A tree is height-balanced when every node in the tree has a balance that is −1, 0, or 1. As in the class, we will define the height of a tree recursively. An empty tree has a height of −1. The height of a tree is 1 plus the maximum of the height of the left sub-tree and the height of the right sub-tree. It is fine for you to use the code provided in the lecture notes for this assignment. However, you should re-organize the code. For example, you may want to write separate functions for clockwise rotation and counter-clockwise rotation, and the insertion function will call the appropriate rotation functions. Insertion In the lecture notes, we do not allow duplicate keys in a tree. In this assignment, we allow the insertion of a duplicate key. In other words, the resulting height-balanced may have multiple nodes storing the same key value. Recall that insertion of a key requires you to search for a suitable location to insert a leaf node. To handle nodes storing the same key value, when you search for a leaf node location to insert the key, you should always go left when you encounter a node storing the same key. This requirement is imposed for the grading purpose of this assignment. Deletion When you are asked to delete a key, the tree should stay intact if the key is currently not in the tree. There may be multiple nodes containing the key that you want to delete. You should delete the first such node that you encounter in the search process. If the node you want to delete has two children, you should replace that node with its immediate predecessor (in an in-order traversal of the tree). Again, this requirement is imposed for the grading purpose of this assignment. Tree node structure The tree node structure (Tnode) is defined in the file hbt.h. typedef struct _Tnode { int key; int height; struct _Tnode *left; struct _Tnode *right; } Tnode; The left and right fields store the left and right child nodes of a Tnode, respectively. Two integers int are used to store the tree height and the key of the tree. The integer key stores a signed integer value, whereas the height integer stores the difference in the height of the left sub-tree (left) and ECE36800 Purdue University 1 © Cheng-Kok Koh Due 15th November 11:59 PM the height of the right sub-tree (right). A correctly implemented height-balanced tree insertion or deletion routine should not allow the balance of a node to go below −2 or above 2. You should include this file in your other .h and .c files that you will develop for this assignment. This file will be provided when we compile your submission. You do not have to submit this file. In your other .h and .c, you should not define other structures. No other user-defined structures are allowed in this assignment. If you have other user-defined structure(s) in your .h and/or .c files, your submission will not be graded. Deliverables In this assignment, you are required to develop other include file(s) (in addition to the provided hbt.h) and source file(s), which can be compiled with the following command: gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa4 It is recommended that while you are developing your program, you use the “-g” flag instead of the “-O3” flag for compilation so that you can use a debugger if necessary. There are two options that the executable pa4 can accept. The main function should simply return EXIT FAILURE if the argument count is incorrect or the options are invalid (see further details below). Option "-b": Building a height-balanced BST ./pa4 -b operations input file tree output file The option "-b" means that you are building a height-balanced BST (starting from an empty tree) based on the operations specified in operations input file. Input file format The operations input file is an input file in binary format. Every operation is specifed by (sizeof(int) + sizeof(char)) bytes, with the first sizeof(int) bytes being an int and the next sizeof(char) byte being a char. The int is the key. If it is an insertion of the specified key, the char is an ASCII character ’i’. If it is a deletion of the specified key, the char is an ASCII character ’d’. If there are n keys to be inserted or deleted, the file size is n× (sizeof(int)+sizeof(char)) bytes. Output file format The tree output file is an output file in binary format. This file stores the pre-order traversal of the constructed height-balanced BST. Each non-NULL node is represented by an int and a char. The int is the key stored in the node. The char is a binary pattern, with the least significant two bits capturing the types of branches that node has. At bit position 0 (the least significant bit position), a 0-bit means that the right branch of the node is NULL. A 1-bit means that the right branch of the node is a non-NULL node. At bit position 1 (the second least significant bit position), a 0-bit means that the left branch of the node is NULL. A 1-bit means that the left branch of the node is a non-NULL. All other more significant bits in the char should be 0. Therefore, a numerical value of 2 or 3 (in decimal) for the binary pattern stored in the char means there is a left child. A numerical value of 1 or 3 (in decimal) means that there is a right child. A numerical value of 0 means that there are no child nodes. ECE36800 Purdue University 2 © Cheng-Kok Koh Output and return value of main function If the given input file can be opened, your program should attempt to build a height-balanced BST. If the given input file cannot be opened, the program should print the value -1 (using the format "%d\n") to the stdout and return EXIT FAILURE. Now, suppose the given input file can be opened. If in the process of building the height-balanced BST, your program encounters a problem in the input file (wrong format, for example) or a failure in memory allocation, you should still write to the output file the tree that has been contructed so far. You should print the value 0 (using the format "%d\n") to the stdout and return EXIT FAILURE. We will test your program with valid input files of reasonable sizes. Therefore, it is unlikely that you will have to print the value 0 to the stdout. If you can successfully read the entire input file to build a tree, you should print the value 1 (using the format "%d\n") to the stdout and return EXIT SUCCESS; your program should return EXIT FAILURE otherwise. We are not asking you to check whether you can write to the output file. We will use the option "-e" to evaluate that. Option "-e": Evaluating a height-balanced BST ./pa4 -e tree input file The option "-e" means that you are evaluating a tree specified in the tree input file. The tree input file is actually of the same format as the output produced using the "-b" option. For the given tree input file, your program should print three integers to stdout using the format "%d,%d,%d\n", where the first integer indicates the validity of the input file, the second integer indicates whether the tree is a BST, and the third integer indicates whether the tree is a height-balanced tree. If the input file cannot be opened, the first integer should be -1. If it can be opened, but of the wrong format, the first integer should be 0. If it can be opened and is of the correct format, the first integer should be 1. If the input file is a valid tree, the second and third integers are meaningful (otherwise, their values are not important). If the tree is a BST, the second integer is 1; otherwise, it is 0. If the tree is height-balanced, the third integer is 1; otherwise, it is 0. The main function should return EXIT SUCCESS only if the input file is valid (i.e., the first integer of the terminal output is 1); your program should return EXIT FAILURE otherwise. Electronic Submission The project requires the submission (electronically) of the C-code (source and include files) through Brightspace. You should create and submit a zip