Program must be done in C!

In this assignment you will modify the binary search tree code studied in class to:

Support several new features (some with runtime requirements) and

Enforce a balancing property ("size-balancing") which results in amortized logarithmic runtime for insertion and deletion (and all operations that take time proportional to the tree height are O(log n) in the worst case.

NOTE: Although described as two parts, they may be implemented in either order: part 2 does not really depend on part-1 (although they will both probably rely on the bookkeeping information you).

(1) Additional Features

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).

Bookkeeping Info Hint: keeping track of the number of nodes in each subtree might come in handy!

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 *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 *t, int i);

/* returns the value in the tree closest to x -- in other

words, some y in the tree 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 *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 *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 *t, int x);

/* returns the number of elements in t which are between min

and max (inclusive).

Runtime: O(h) where h is the tree height

*/

extern int bst_num_range(BST *t, int min, int max);

Pre-existing functions needing modification:

Three pre-existing functions either modify an existing tree or build one from scratch You will need to change them so that they also make sure that the bookkeeping information is correct. The relevant functions are:

int bst_remove(BST * t, int x);

int bst_insert(BST * t, int x);

BST * bst_from_sorted_arr(int *a, int n);

The runtime of these bst_remove and bst_insert must still be O(h); the runtime of bst_from_sorted_arr must still be O(n).

Comment: once you have completed part-2 (size-balancing), these runtime bounds will become O(log n) because in a size-balanced tree, the height is guaranteed to be O(log n)

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 youve 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.

HINT: some of the logic employed in the previously studied QuickSelect algorithm may be handy (not the entire algorithm per-se, but its underlying logic

(2) "Size-Balancing"

In this part of the assignment you will implement the size-balanced strategy described below.

As we know, "vanilla" BSTs do not in general guarantee logarithmic height and as a result, basic operations like lookup, insertion and deletion are linear time in the worst case. There are ways to fix this weakness -- e.g., AVL trees and Red-Black trees. We will not be doing either of those; instead, you will implement the "size-balanced" strategy described below.

The size-balanced property:

The size-balanced property:

Definition (size-balance property for a node) Consider a node v in a binary tree with nL nodes in its left subtree and nRnodes in its right subtree; we say that v is size-balanced if and only if:

max(nL, nR) 2min(nL, nR) + 1

(so roughly, an imbalance of up to - is allowed)

Definition: (size-balance property for a tree). We say that a binary tree t is size-balanced if and only if all nodes v in t are size-balanced

Your implementation must ensure that the tree is always size-balanced. Only the insert and delete operations can result in a violation.

When an operation which modifies the tree (an insert or delete) results in a violation, you must rebalance the violating node/subtree closest to the root

You do not in general want to rebalance at the root each time there is a violation (only when there is a violation at the root).

Amortized Claim: As it turns out, while every now and then we may have to do an expensive rebalancing operation, a sequence of m operations will still take O(mlog n) time -- or O(log n) on average for each of the m operations. Thus, it gives us performance as good as AVL trees (and similar data structures) in an amortized sense.

Strategy/Suggestions:

A straightforward approach to rebalancing a subtree is as follows:

Populate a temporary array with the elements/nodes in the subtree in sorted order.

From this array, re-construct a perfectly balanced (as perfectly as possible) tree to replace the original tree.

The details are up to you, but observe that the number of tree nodes before and after the re-balancing is unchanged, you should be able to re-use the already existing nodes.

Statistics function:

You will also implement a function which reports the total "work" done by re-balancing. Every time you do a re-balance, the cost or work performed is the size of the sub-tree that was rebalanced.

You will keep track of the total amount of rebalancing work performed and report it via the following function:

/**

* function: bst_sb_work

* description: returns the total amount of work performed by re-balancing

* since the creation of the tree.

* Every time a rebalance operation happens, the work

* is equal to the size of the subtree that was rebalanced

* (size=number-of-nodes).

* The total work is simply taken over all re-balancing ops.

*/

extern int bst_sb_work(BST *t);

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).

---------------------------------------bst.c---------------------------------------------

#include "bst.h" #include  #include  struct bst_node { int val; struct bst_node *left; struct bst_node *right; }; typedef struct bst_node NODE; struct bst { NODE *root; }; BST * bst_create(){ BST * 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 * 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 * t, int x){ t->root = insert(t->root, x); } int bst_contains(BST * 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 * 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 * 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 * t){ return height(t->root); } int bst_min(BST * t){ return min_h(t->root); } int bst_max(BST * t){ return max_h(t->root); } static void indent(int m){ int i; for(i=0; ileft); printf("[%d] ", r->val); inorder(r->right); } void bst_inorder(BST * 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 * 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 * 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 * bst_from_sorted_arr(int *a, int n){ BST * t = bst_create(); t->root = from_arr(a, n); return t; } 

-------------------------------------------------------------------bts.h----------------------------------------

// typedef int ELEM_TYPE; typedef struct bst BST; extern BST * bst_create(); extern void bst_free(BST * t); /** TODO: modify for augmentations and size-balancing **/ extern void bst_insert(BST * t, int x); /** TODO: modify for augmentations and size-balancing **/ extern int bst_remove(BST * t, int x); extern int bst_contains(BST * t, int x); /** NOTE: not part of the assignment, but you should be able to make bst_size O(1) trivially once everything else is in place. */ extern int bst_size(BST * t); extern int bst_height(BST * t); extern int bst_min(BST * t); extern int bst_max(BST * t); /************************************************************/ extern void bst_inorder(BST * t); extern void bst_preorder(BST * t); extern void bst_postorder(BST * t); extern BST * bst_from_sorted_arr(int *a, int n); /*** TODO ***/ extern int * bst_to_array(BST * t); extern int bst_get_ith(BST * t, int i); extern int bst_get_nearest(BST * t, int x); extern int bst_num_geq(BST * t, int x); extern int bst_num_leq(BST * t, int x); extern int bst_num_range(BST * t, int min, int max); extern int bst_sb_work(BST *t); 

---------------------------------------bst_doc.c-------------------------------

#include "bst.h" #include  #include  struct bst_node { int val; struct bst_node *left; struct bst_node *right; }; typedef struct bst_node NODE; struct bst { NODE *root; }; /** * function: bst_create() * desc: allocates and initizlizes * an empty BST and returns it as * a BST pointer. */ BST * bst_create(){ BST * t = malloc(sizeof(struct bst)); t->root = NULL; return t; } /** * function: free_r() * desc: recursive helper function deallocating * the nodes of a tree rooted at NODE r */ static void free_r(NODE *r){ if(r==NULL) return; free_r(r->left); free_r(r->right); free(r); } /** * function: bst_free() * desc: deallocates all storage associated with * BST given by t. */ void bst_free(BST * t){ free_r(t->root); free(t); } /** * function: insert() * desc: recursive helper function inserting x into * binary search tree rooted at r. * * returns: pointer to root of tree after insertion. * * notes: if x is already in tree, no modifications are made. */ 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; } } // placeholder for unimplemented iterative // insertion routing. static NODE *insert_i(NODE *r, int x){ return NULL; } /** * function: bst_insert() * desc: inserts x into BST given by t. Note that * a BST stores a SET -- no duplicates. Thus, * if x is already in t when call made, no * modifications to tree result. * * note: helper function does most of the work. * */ void bst_insert(BST * t, int x){ t->root = insert(t->root, x); } /** * function: bst_contains() * desc: returns 0 or 1 depending on whether x is an * element of BST given by pointer t. * */ int bst_contains(BST * 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; } /** * function: min_h() * desc: helper function returning the minimum value * stored in tree rooted at r. * * notes: this is a local helper function and it is * presumed that it will be called on a non-null * node pointer r. (An empty tree has no meaningful * minimum value). */ static int min_h(NODE *r){ if(r==NULL) return -1; // should never happen! while(r->left != NULL) r = r->left; return r->val; } /** * function: max_h() * desc: helper function returning the maximmum value * stored in tree rooted at r. * * notes: this is a local helper function and it is * presumed that it will be called on a non-null * node pointer r. (An empty tree has no meaningful * maximum value). */ static int max_h(NODE *r){ if(r==NULL) return -1; // should never happen! while(r->right != NULL) r = r->right; return r->val; } /** * function: remove_r() * desc: recursive function implementing the * "deletion by copying" approach to BST deletion. * * params: r - root of tree for deletion * x - value to delete (if it is in tree of course) * success - used to communicate if a deletion actually * occurred. *success is set to 0 on failure; 1 on success. * * return: returns root of resulting tree after deletion. */ 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); // overwrite x with min elem from right subtree // now we have two copies of the value from previous statement. // recursively get rid of the original one! r->right = remove_r(r->right, r->val, &sanity); if(!sanity) printf("ERROR: remove() failed to delete promoted value? "); return r; } // if we get here, r->val did not match x - go left or right accordingly if(x < r->val){ r->left = remove_r(r->left, x, success); } else { r->right = remove_r(r->right, x, success); } return r; } /** * function: bst_remove() * desc: if x is an element of BST given by pointer t, * it is removed, and 1 (for success) is returned. * Otherwise (x not an element of tree), the tree is * unchanged and 0 (for failure is returned). * * note: helper function remove_r does most of the work. * */ int bst_remove(BST * t, int x){ int success; t->root = remove_r(t->root, x, &success); return success; } /** * function: size() * desc: static function computing the number of nodes * in the tree given by NODE pointer r. * Number of nodes is returned * * method: brute force traversal of tree recursively couting * up nodes. */ static int size(NODE *r){ if(r==NULL) return 0; return size(r->left) + size(r->right) + 1; } /** * function: bst_size() * desc: returns number of nodes/elements in given * BST. */ int bst_size(BST * t){ return size(t->root); } /** * function: height() * desc: returns the height of the tree given * by NODE pointer r. * * method: recursive traversal of tree computing subtree * heights from results of recursive calls. * * notes: this is a recursive helper function operating * at the "node level"; called by bst_height. */ 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); } /** * function: bst_height() * desc: returns the height of the tree given * by BST pointer t. * * note: helper function height() does most of the work. */ int bst_height(BST * t){ return height(t->root); } /** * function: bst_min() * desc: returns the minimum element stored in BST * given by pointer t. * * exception: if tree is empty, an arbitrary value is returned. * Caller should not rely on such a value having anyu * real meaning (and should just invoke this function * on only non-empty trees). * * note: helper function min_h() does most of the work. */ int bst_min(BST * t){ return min_h(t->root); } /** * function: bst_max() * desc: returns the maximum element stored in BST * given by pointer t. * * exception: if tree is empty, an arbitrary value is returned. * Caller should not rely on such a value having anyu * real meaning (and should just invoke this function * on only non-empty trees). * * note: helper function max_h() does most of the work. */ int bst_max(BST * t){ return max_h(t->root); } /** * function: indent() * desc: utility function simply printing * m dashes ('-') without a new line. * * notes: used for printing trees where level of indentation * indicates distance from root. */ static void indent(int m){ int i; for(i=0; ileft); printf("[%d] ", r->val); inorder(r->right); } /** * function: bst_inorder() * desc: prints the elements of BST given by pointer t "in-order" * notes: recursive helper function inorder does most of the work */ void bst_inorder(BST * t){ printf("========BEGIN INORDER============ "); inorder(t->root); printf("=========END INORDER============ "); } /** * function: preorder() * desc: prints the elements of tree rooted at r according to * standard "pre-order" traversal according to the description * of bst_preorder */ 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); } } /** * function: bst_preorder() * desc: prints the elements of BST given by pointer t according to * standard "pre-order" traversal. * * Elements are printed one-per-line and are indented to * indicate the tree structure: * root has indentation zero * child nodes are indented "one level" past the * indentation of their parents. * Thus, all elements at the same distance from the root * are indented exaclty the same. */ void bst_preorder(BST * t){ printf("========BEGIN PREORDER============ "); preorder(t->root, 0); printf("=========END PREORDER============ "); } /* * func: postorder * desc: placeholder for unimplemented recursive postorder printing * function at the "node level" * * indentation should be proportional to depth of node being printed * depth is #hops from root. */ static void postorder(NODE *r, int margin){ /* FILL IN FUNCTION */ } /* * func: bst_postorder * desc: prints elements of BST given by pointer t in "post-order". * Indentation is proportional to depth of node being printed. * Depth is #hops from root. * * Notes: depends on helper function postorder which is currently * unimplemented. */ void bst_postorder(BST * t){ printf("========BEGIN POSTORDER============ "); postorder(t->root, 0); printf("=========END POSTORDER============ "); } /* * func: from_arr * desc: recursive helper function from_arr which constructs a perfectly * balanced tree (at the "node level") from the values stored in * array a. * * requirement: given array a is assumed to be in sorted order. * * returns: returns pointer to root of resulting balanced tree. */ 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; } /* * func: bst_from_sorted_arr * desc: builds a BST which is as balanced as possible from sorted array a. * * precondition: given array a is assumed to be sorted and have no duplicates. * Assumed to be the caller's responsiblity to ensure these * properties. * * notes: helper function from_arr does most of the work. */ BST * bst_from_sorted_arr(int *a, int n){ BST * t = bst_create(); t->root = from_arr(a, n); return t; 

}