In this assignment you will modify the binary search tree code used in lab to su
ID: 3760072 • Letter: I
Question
In this assignment you will modify the binary search tree code used in lab to support several new features (some with runtime requirements).
These features will require augmentation of the existing data structures with additional book-keeping information. This bookkeeping info must be kept up to date incrementally; as a result you will have to modify some existing functions (insert, delete, build-from-array).
Now to the new functions/features:
/* allocates an integer array, populates it with the
elements of t (in-order) and returns the array as an
int pointer */
extern int * bst_to_array(BST_PTR t);
/* returns the ith smallest element in t. i ranges
from 1..n where n is the number of elements in
the tree.
If i is outside this range, an error message is printed
to stderr and the return value is arbitrary (you may return
whatever you like, but it has no meaning.
Runtime: O(h) where h is the tree height
*/
extern int bst_get_ith(BST_PTR t, int i);
/* returns the value in the tree closest to x -- in other
words, some y in the three where |x-y| is minimum.
If the tree is empty, a message is sent to stderr and
the return value is of your choosing.
Runtime: O(h) where h is the tree height.
*/
extern int bst_get_nearest(BST_PTR t, int x);
/* returns the number of elements in t which are greater
than or equal to x.
Runtime: O(h) where h is the tree height
*/
extern int bst_num_geq(BST_PTR t, int x);
/* returns the number of elements in t which are less
than or equal to x.
Runtime: O(h) where h is the tree height
*/
extern int bst_num_leq(BST_PTR t, int x);
Additional runtime requirement:
Modify the size function to have O(1) runtime.
Functions needing modification:
The insert and remove functions modify the tree. You will need to change them so that they also make sure that the bookkeeping information is correct.
The runtime of these functions must still be O(h)
Submission: you will submit bst.c and a README file (see below) in a single archive file.
Comments/Suggestions:
You will need to augment the NODE struct. This is perfectly fine since it is in the .c file and not the .h file.
I recommend you write a sanity-checker function which, by brute force, tests whether the bookkeeping information you’ve maintained is indeed correct.
Of course, you should write extensive test cases. You are free to share test cases with classmates. You might try valgrind to also look for memory errors.
modifying your implementation so that the bst_min and bst_max functions to operate in O(1) time.
Note that you will almost certainly need to modify more than just those functions to make this work.
Readme File:
To make grading more straightforward (and to make you explain how you achieved the assignment goals), you must also submit a Readme file.
The directory containing the source files and this handout also contains a template Readme file which you should complete (it is organized as a sequence of questions for you to answer).
Open in Drive
Assignments › ... › src
3 items
bst.c
bst.h
test.c
bst.h
Explanation / Answer
#include "bst.h"
#include <stdio.h>
#include <stdlib.h>
struct bst_node {
int val;
struct bst_node *left;
struct bst_node *right;
};
typedef struct bst_node NODE;
struct bst {
NODE *root;
};
BST_PTR bst_create(){
BST_PTR t = malloc(sizeof(struct bst));
t->root = NULL;
return t;
}
static void free_r(NODE *r){
if(r==NULL) return;
free_r(r->left);
free_r(r->right);
free(r);
}
void bst_free(BST_PTR t){
free_r(t->root);
free(t);
}
static NODE * insert(NODE *r, int x){
NODE *leaf;
if(r == NULL){
leaf = malloc(sizeof(NODE));
leaf->left = NULL;
leaf->right = NULL;
leaf->val = x;
return leaf;
}
if(r->val == x)
return r;
if(x < r->val){
r->left = insert(r->left, x);
return r;
}
else {
r->right = insert(r->right, x);
return r;
}
}
// how about an iterative version?
static NODE *insert_i(NODE *r, int x){
return NULL;
}
void bst_insert(BST_PTR t, int x){
t->root = insert(t->root, x);
}
int bst_contains(BST_PTR t, int x){
NODE *p = t->root;
while(p != NULL){
if(p->val == x)
return 1;
if(x < p->val){
p = p->left;
}
else
p = p->right;
}
return 0;
}
static int min_h(NODE *r){
if(r==NULL)
return -1; // should never happen!
while(r->left != NULL)
r = r->left;
return r->val;
}
static int max_h(NODE *r){
if(r==NULL)
return -1; // should never happen!
while(r->right != NULL)
r = r->right;
return r->val;
}
static NODE *remove_r(NODE *r, int x, int *success){
NODE *tmp;
int sanity;
if(r==NULL){
*success = 0;
return NULL;
}
if(r->val == x){
*success = 1;
if(r->left == NULL){
tmp = r->right;
free(r);
return tmp;
}
if(r->right == NULL){
tmp = r->left;
free(r);
return tmp;
}
// if we get here, r has two children
r->val = min_h(r->right);
r->right = remove_r(r->right, r->val, &sanity);
if(!sanity)
printf("ERROR: remove() failed to delete promoted value? ");
return r;
}
if(x < r->val){
r->left = remove_r(r->left, x, success);
}
else {
r->right = remove_r(r->right, x, success);
}
return r;
}
int bst_remove(BST_PTR t, int x){
int success;
t->root = remove_r(t->root, x, &success);
return success;
}
static int size(NODE *r){
if(r==NULL) return 0;
return size(r->left) + size(r->right) + 1;
}
int bst_size(BST_PTR t){
return size(t->root);
}
static int height(NODE *r){
int l_h, r_h;
if(r==NULL) return -1;
l_h = height(r->left);
r_h = height(r->right);
return 1 + (l_h > r_h ? l_h : r_h);
}
int bst_height(BST_PTR t){
return height(t->root);
}
int bst_min(BST_PTR t){
return min_h(t->root);
}
int bst_max(BST_PTR t){
return max_h(t->root);
}
static void indent(int m){
int i;
for(i=0; i<m; i++)
printf("-");
}
static void inorder(NODE *r){
if(r==NULL) return;
inorder(r->left);
printf("[%d] ", r->val);
inorder(r->right);
}
void bst_inorder(BST_PTR t){
printf("========BEGIN INORDER============ ");
inorder(t->root);
printf("=========END INORDER============ ");
}
static void preorder(NODE *r, int margin){
if(r==NULL) {
indent(margin);
printf("NULL ");
} else {
indent(margin);
printf("%d ", r->val);
preorder(r->left, margin+3);
preorder(r->right, margin+3);
}
}
void bst_preorder(BST_PTR t){
printf("========BEGIN PREORDER============ ");
preorder(t->root, 0);
printf("=========END PREORDER============ ");
}
/*
* Complete the (recursive) helper function for the post-order traversal.
* Remember: the indentation needs to be proportional to the height of the node!
*/
static void postorder(NODE *r, int margin){
/* FILL IN FUNCTION */
}
// indentation is proportional to depth of node being printed
// depth is #hops from root.
void bst_postorder(BST_PTR t){
printf("========BEGIN POSTORDER============ ");
postorder(t->root, 0);
printf("=========END POSTORDER============ ");
}
/*
* Write the (recursive) helper function from_arr, used by
* bst_from_sorted_arr(...). The function must return a sub-tree that is
* perfectly balanced, given a sorted array of elements a.
*/
static NODE * from_arr(int *a, int n){
int m;
NODE *root;
if(n <= 0) return NULL;
m = n/2;
root = malloc(sizeof(NODE));
root->val = a[m];
root->left = from_arr(a, m);
root->right = from_arr(&(a[m+1]), n-(m+1));
return root;
}
BST_PTR bst_from_sorted_arr(int *a, int n){
BST_PTR t = bst_create();
t->root = from_arr(a, n);
return t;
}
bst.h
// typedef int ELEM_TYPE;
typedef struct bst *BST_PTR;
extern BST_PTR bst_create();
extern void bst_free(BST_PTR t);
/** TODO: modify for augmentations **/
extern void bst_insert(BST_PTR t, int x);
/** TODO: modify for augmentations **/
extern int bst_remove(BST_PTR t, int x);
extern int bst_contains(BST_PTR t, int x);
/** TODO: make O(1) **/
extern int bst_size(BST_PTR t);
extern int bst_height(BST_PTR t);
/** EXTRA CREDIT: bst_min and bst_max modified to be O(1)
These will require modification of other functions.
They are not terribly difficult but since they are
extra credit, you are REQUIRED to include a separate
README file which does the following:
- states that you did indeed complete the functions.
- what other functions needed to be modified and
a description of the mofifications. This should
include an argument that the runtime of those
functions has not been altered.
Points: These will account for (only) a 10% bonus if working
correclty.
**/
extern int bst_min(BST_PTR t);
extern int bst_max(BST_PTR t);
/************************************************************/
extern void bst_inorder(BST_PTR t);
extern void bst_preorder(BST_PTR t);
extern void bst_postorder(BST_PTR t);
extern BST_PTR bst_from_sorted_arr(int *a, int n);
/*** TODO ***/
extern int * bst_to_array(BST_PTR t);
extern int bst_get_ith(BST_PTR t, int i);
extern int bst_get_nearest(BST_PTR t, int x);
extern int bst_num_geq(BST_PTR t, int x);
extern int bst_num_leq(BST_PTR t, int x);