// For size_t /* Type: struct Node A type representing a node in a binary search tree. * The keys are integers. struct Node { int value; struct Node* left; struct Node* right; }; /** * Inserts a new value into the binary search tree whose root pointer is pointed * at by root. The behavior of this function is unspecified in the case * where memory for a new node can't be allocated or if root is NULL. * This function does not make any attempt to balance the tree. It simply inserts * the element in to the BST following the standard insertion algorithm. This may lead to significantly imbalanced trees. *
* If the specified value already exists in the given BST, this function has no * effect and does not change the underlying BST. @param root The root of the tree, which may be updated. @param value The value to insert. void insert_into(struct Node** root, int value); /** * Deallocates all memory associated with the indicated binary search tree. * @param root The root of the tree to free. void free_tree (struct Node* root); /** * Returns the number of elements in the binary search tree pointed at by root. * @param root The root of the tree in question. * @return The number of elements in that tree. size_t size_of(const struct Node* root); /** * Returns a dynamically-allocated array containing the contents of the tree * in sorted order. The behavior of this function is unspecified in the case where the appropriate memory can't be obtained. * @param root A pointer to the root of the tree. @return An array of the tree's elements, in sorted order. int* contents of (const struct Node* root); /** * Returns a pointer to the node in the specified tree containing the second- * smallest element in the tree. If the tree has zero or one elements, this * function returns NULL. @param root The root of the tree in question. @return A pointer to the node holding the second-smallest element in the tree, or NULL if such a node doesn't exist. */ const struct Node* second_min_in(const struct Node* root); Fendi #include "bst.h" #include #include #include #include #include #include #include #include /* Type: FileData * A type representing tree data read from the file. It consists of a pair of a number of elements and the elements themselves, in order. */ struct FileData { size_t num_elems; int* elems; /* Constant: TEST_DIRECTORY * Name of the directory containing test cases to run. This must end with a * slash. */ #define TEST_DIRECTORY "tests/" /* Macro: error(msg) * Reports an error and terminates the program. */ #define error(msg) do_error(msg, __FILE__, _LINE_) static void do_error(const char* msg, const char* file, unsigned line) { fprintf(stderr, "ERROR: %s File: %s Line: %u ", msg, file, line); abort(); /* Function: read_file(filename) Returns the contents of a tree test file as a FileData object. On error, aborts the program. */ static struct FileData read_file(const char* test_file) { struct FileData result; FILE* f = fopen(test_file, "r"); if (f == NULL) error("Can't open test file."); /* Read the tree contents into a separate buffer so that we can see whether everything worked * properly. */ if (fscanf(f, "%zu", &result.num_elems) != 1) error("Failed to read number of elements from file."); result.elems = calloc(result.num_elems, sizeof(int)); for (size_t i = 0; i right) return +1; return 0; } /* Function: assert_monotone_increasing(data, size) * --- * Asserts that the range pointed at by data is monotonically increasing (each * element is strictly greater than the previous.) static void assert_monotone_increasing(const int* data, size_t size) { for (size_t i = 1; i = data[i]) { fprintf(stderr, "Elements not strictly increasing: %d >= %d ", data[i-1], data[i]); abort(); } } /* Function: advance(data, size, &index) Advances the index value forward in the data range until it either hits the * end of the range or encounters a different value. It is assumed that the * index is purely before the end of the range, since otherwise this is not * mathematically well-defined. */ static void advance(const int* data, size_t size, size_t* index) { size_t result = *index + 1; while (result data2[i2]) { fprintf(stderr, "Mismatch found: second range contains %d, second does not. ", data2[i2]); abort(); } /* Advance each pointer forward until it either hits the range end or no * longer points at an equal value. advance(datal, sizel, il); advance(data2, size2, &i2); } /* Both ranges should be empty at this point. */ if (il value); } free_tree(root); free (data.elems); free(tree_elems); } int main() { DIR* tests = opendir(TEST_DIRECTORY); if (tests == NULL) error("Could not open " TEST_DIRECTORY " for reading."); for (struct dirent* entry; (entry = readdir(tests)) != NULL; ) { /* Make sure this isn't a dotted file (hidden file, ., or..) */ if (entry->d_name[@] == '.') continue; char tes filer [strlen(entry->d_name) + strlen(TEST_DIRECTORY) + 1]; strcpy(test_file_name, TEST_DIRECTORY); strcat(test_file_name, entry->d_name); run_test(test_file_name); if (errno != 0) error("Error traversing the " TEST_DIRECTORY " directory."); closedir(tests); return; } Algorithmic Prerequisites Problem One: Binary Search Trees Binary search trees are versatile and flexible data structures, and we'll explore their many properties over the semester. In the course of doing so, we'll get to see some cool ideas from Theoryland. Before we do that, though, I want to make sure everyone has a chance to refresh some of the core concepts from BSTS. To complete this part of the assignment, you will need to ssh into the vm that I've setup for this class and download the starter files from: screenshots of files shown and implement the bst.c source file's functions. (That folder houses the raw files; there's no git repository there, so use cp -r rather than git clone to copy the files.) Test your implementation extensively. You may want to use the provided test harness as a starting point. Feel free to add your own tests on top of mine. To receive credit on this part of the assignment, your code should compile with no warnings (eg., compiled with -Wall-Werror) and should run cleanly under valgrind (that is, you should have no memory errors or memory leaks). I will run your code on the myth machines, so I recommend you test there before submitting i Implement a function void insert_into (struct Node** root, int value); that inserts the specified value into the given BST if it doesn't already exist. Your algorithm should run in time 0(h), where h is the height of the tree. (You can assume that root is not NULL, though *root can be NULL when the BST you're inserting into is empty.) You should not attempt to bal ance the tree. ii. Implement a function void free_tree (struct Node* root); that deallocates all memory associated with the specified tree. Your function should run in time (n), where n is the number of nodes in the tree. 111. Implement a function size_t size_of (const struct Node* root); that returns the number of nodes in the specified tree. Your function should run in time (n). where n is the number of nodes in the tree. iv. Implement a function int* contents of (const struct Node* root); that returns a pointer to a dynamically-allocated array containing the elements of that BST in sorted order. Your function should run in time (n), where n is the number of nodes in the tree. v. Implement a function const struct Node* second_min_in(const struct Node* root); that returns a pointer to the second-smallest element of the given BST, or NULL if the tree doesn't have at least two elements. Your function should run in time 0(h), where h is the tree height. #include "bst.h" #include // For NULL #include // For malloc, free void insert_into(struct Node** root, int value) { /* TODO: Implement this function! */ (void) root; (void) value; void free_tree(struct Node* root) { /* TODO: Implement this function! */ (void) root; size_t size_of(const struct Node* root) { /* TODO: Implement this function! */ (void) root; return 0; int* contents of (const struct Node* root) { /* TODO: Implement this function! */ (void) root; return NULL; } const struct Node* second_min_in(const struct Node* root) { /* TODO: Implement this function! */ (void) root; return NULL; #ifndef BST_Included #define BST_Included #include // For size_t /* Type: struct Node A type representing a node in a binary search tree. * The keys are integers. struct Node { int value; struct Node* left; struct Node* right; }; /** * Inserts a new value into the binary search tree whose root pointer is pointed * at by root. The behavior of this function is unspecified in the case * where memory for a new node can't be allocated or if root is NULL. * This function does not make any attempt to balance the tree. It simply inserts * the element in to the BST following the standard insertion algorithm. This may lead to significantly imbalanced trees. *
* If the specified value already exists in the given BST, this function has no * effect and does not change the underlying BST. @param root The root of the tree, which may be updated. @param value The value to insert. void insert_into(struct Node** root, int value); /** * Deallocates all memory associated with the indicated binary search tree. * @param root The root of the tree to free. void free_tree (struct Node* root); /** * Returns the number of elements in the binary search tree pointed at by root. * @param root The root of the tree in question. * @return The number of elements in that tree. size_t size_of(const struct Node* root); /** * Returns a dynamically-allocated array containing the contents of the tree * in sorted order. The behavior of this function is unspecified in the case where the appropriate memory can't be obtained. * @param root A pointer to the root of the tree. @return An array of the tree's elements, in sorted order. int* contents of (const struct Node* root); /** * Returns a pointer to the node in the specified tree containing the second- * smallest element in the tree. If the tree has zero or one elements, this * function returns NULL. @param root The root of the tree in question. @return A pointer to the node holding the second-smallest element in the tree, or NULL if such a node doesn't exist. */ const struct Node* second_min_in(const struct Node* root); Fendi #include "bst.h" #include #include #include #include #include #include #include #include /* Type: FileData * A type representing tree data read from the file. It consists of a pair of a number of elements and the elements themselves, in order. */ struct FileData { size_t num_elems; int* elems; /* Constant: TEST_DIRECTORY * Name of the directory containing test cases to run. This must end with a * slash. */ #define TEST_DIRECTORY "tests/" /* Macro: error(msg) * Reports an error and terminates the program. */ #define error(msg) do_error(msg, __FILE__, _LINE_) static void do_error(const char* msg, const char* file, unsigned line) { fprintf(stderr, "ERROR: %s File: %s Line: %u ", msg, file, line); abort(); /* Function: read_file(filename) Returns the contents of a tree test file as a FileData object. On error, aborts the program. */ static struct FileData read_file(const char* test_file) { struct FileData result; FILE* f = fopen(test_file, "r"); if (f == NULL) error("Can't open test file."); /* Read the tree contents into a separate buffer so that we can see whether everything worked * properly. */ if (fscanf(f, "%zu", &result.num_elems) != 1) error("Failed to read number of elements from file."); result.elems = calloc(result.num_elems, sizeof(int)); for (size_t i = 0; i right) return +1; return 0; } /* Function: assert_monotone_increasing(data, size) * --- * Asserts that the range pointed at by data is monotonically increasing (each * element is strictly greater than the previous.) static void assert_monotone_increasing(const int* data, size_t size) { for (size_t i = 1; i = data[i]) { fprintf(stderr, "Elements not strictly increasing: %d >= %d ", data[i-1], data[i]); abort(); } } /* Function: advance(data, size, &index) Advances the index value forward in the data range until it either hits the * end of the range or encounters a different value. It is assumed that the * index is purely before the end of the range, since otherwise this is not * mathematically well-defined. */ static void advance(const int* data, size_t size, size_t* index) { size_t result = *index + 1; while (result data2[i2]) { fprintf(stderr, "Mismatch found: second range contains %d, second does not. ", data2[i2]); abort(); } /* Advance each pointer forward until it either hits the range end or no * longer points at an equal value. advance(datal, sizel, il); advance(data2, size2, &i2); } /* Both ranges should be empty at this point. */ if (il value); } free_tree(root); free (data.elems); free(tree_elems); } int main() { DIR* tests = opendir(TEST_DIRECTORY); if (tests == NULL) error("Could not open " TEST_DIRECTORY " for reading."); for (struct dirent* entry; (entry = readdir(tests)) != NULL; ) { /* Make sure this isn't a dotted file (hidden file, ., or..) */ if (entry->d_name[@] == '.') continue; char tes filer [strlen(entry->d_name) + strlen(TEST_DIRECTORY) + 1]; strcpy(test_file_name, TEST_DIRECTORY); strcat(test_file_name, entry->d_name); run_test(test_file_name); if (errno != 0) error("Error traversing the " TEST_DIRECTORY " directory."); closedir(tests); return; }
