Description

Lab Assignment 5 CS 302 – Advanced Data Structures and File Processing Fall 2019 Problem 1 The goal of this problem is to design a data structure that manages the values in a given array A. It shall be able to update these values and compute sums of values quickly. For this purpose, we construct a tree T where each element of A is represented by a leave of T. All leaves are on the same layer and T should only have leaves that represent elements of A. The order of the leaves is also the order of corresponding elements in A. As a result, T is balanced. Some inner nodes of T might have a null-pointer as subtree if the size of A is not a power of 2. An example is given below. A 0 1 2 3 4 Each node of T stores three integer values: – sum. Stores the sum of all elements managed by the subtree rooted in the node. – min and max. The minimum and maximum index in A of the elements managed by the subtree rooted in the node. Note that, for a leaf representing A[i], min = max = i and sum = A[i]. Implement the following operations of the data structure. We assume that the given array has size n. – buildTree(int[] arr). Builds the tree (structure of nodes) as described above and returns the root of the created tree. Hint: Build the tree bottom up, layer by layer. For each layer, take the nodes of the previous layer and build pairs. Continue until a layer has only one node left. – add(int index, int val). Add the value val to the number with the corresponding index. – sum(int index). Return the sum of the first numbers up to the given index, i. e., Pindex j=0 A[j]. There are no insertions or deletions; the only change is to the values of the numbers. The function buildTree should run in O(n) time and the functions add and sum should take O(log n) time. Problem 2 You are given a non-empty binary search tree T (storing integer keys) and a key k stored in T. Let nk be the node in T that stores k. Implement an algorithm that uses rotations to make nk the root of T. The only operations applied to T should be rotations. Afterwards, T should still be a valid binary search tree and store the same set of keys as before. Your algorithm should run in O(h) time where h is the hight of T. Implementation You are given three files (which you can download from canvas): Lab5.java, SumTree.java, and BST.java. The file Lab5.java generates test cases, performs the tests, and outputs the results. The file SumTree.java implements the data structure described in Problem 1. It contains the functions buildTree, add, and sum which you have to implement. The file BST.java partially implements a binary search tree and contains the function problem2. It also contains the functions rotateL, rotateR, and find; feel free to use these functions in your implementation. Do not make any changes outside of the functions buildTree, add, sum, and problem2; such changes will be undone. The program already implemented in the file Lab5.java randomly generates test cases. The seed of the random number generator is set to ensure the same test cases whenever to program is executed. Note that the purpose of the tests is for you to avoid major mistakes. Passing all given tests does not imply that your algorithm is correct, especially that is has the expected runtime. Submission For your submission, upload a single .zip-file containing the files SumTree.java and BST.java with your implementation to canvas. Do not add any other file into your .zip-file; this may affect your grade. This is an individual assignment. Therefore, a submission is required from each student. Deadline: Sunday, November 17, 11:59 p.m.