Description
1 Overview This project involves three important concepts: sets, balanced binary search trees, and maps. • A set is a collection of distinct objects. • A balanced tree represents a set of n elements with a natural ordering so that the running time per operation is O(log n). Depending on the type of balanced tree, this time bound may be worst-case, expected-case, or amortized. • A map is an object that maps a finite set of keys to a collection of values. Each key can map to at most one value, and a map cannot contain duplicate keys. Maps correspond to the mathematical concept of a function. An example of a map is the function that maps the set of student ID numbers (integers) to student names (strings). In this project, you will gain a deeper understanding of these concepts by writing the following two classes. ABTreeSet: An implementation of sets based on α-balanced trees. Any access or update operation on an n-node α-balanced tree takes O(log n) amortized time. ABTreeMap: An implementation of maps that uses α-balanced trees. We will provide you with templates for ABTreeSet and ABTreeMap. You may add new instance variables and methods to these two classes, but you cannot rename or remove any existing variables or methods, or change any of these variables and methods from public to protected (or private), or vice versa. Note. Although the official due date is 11:59 pm, Friday, December 2, you may submit the assignment without penalty until 11:59 pm, Friday, December 9, 2016. 1 2 Introduction The time complexities of the basic operations on a binary search tree —contains(), add(), and remove()— are proportional to the height of the tree. In the ideal case, the height of an n-element tree is at most log2 n. If no precautions are taken, however, the height can be n − 1. There are a number of ways to guarantee that the height of a tree is O(log2 n); they all involve some sort of “rebalancing” after updates, thus these trees are sometimes called self-balancing trees. Self-balancing trees fall into roughly two categories. Height-balanced trees. Here, rebalancing is done to ensure that the heights of the left and right subtrees of any node do not differ by much. Weight-balanced trees. Here, rebalancing is done to ensure that the the sizes (numbers of elements) of the left and right subtrees of any node do not differ by much. Examples of height-balanced trees are AVL-trees,where the heights of the left and right trees at any node differ by at most one, and red-black trees, the heights of the left and right subtrees at any node can differ by a factor of at most two. Red-black trees are used in Java’s implementation of the TreeSet and TreeMap classes. AVL-trees and red-black trees are described in Wikipedia, where you can find links to additional information. We will not discuss height-balanced trees further here. This assignment deals with a special kind of weight-balanced tree, which we describe next. 3 α-Balanced Trees Let T be a binary search tree and let α be a constant, such that 1 2 < α < 1. Let x be any node in T, and size be the number of elements in the subtree rooted at x. We say x is α-balanced if (number of elements in x’s left subtree) ≤ α · size, (1) and (number of elements in x’s right subtree) ≤ α · size. (2) We say the tree T is α-balanced if every node is α-balanced. An α-balanced tree is shown in Figure 1. Simple math shows that the height of an n-node α-balanced tree is at most log1/α n (the idea is to first observe that the size of the subtree rooted at a node at depth k is at most α kn, and that the size of a non-empty subtree is at least 1). Since α is a constant, this means that contains, add, and remove take logarithmic time. However, adding or removing elements can lead to trees that no longer satisfy the balance conditions (1) and (2). α-Balanced trees maintain balance by periodically restructuring entire subtrees, rebuilding them so that they become 1 2 -balanced. The work required for rebalancing is O(n) in the worst case, but it can be shown that the amortized time for an add or remove is O(log n). Although a formal proof of this is beyond the scope of CS 228, the intuition is that rebalancing is relatively rare, in the same way that array doubling is rare in the FirstCollection class that we saw several weeks ago. Next, we explain the rebalancing method used by α-balanced trees, and how rebalancing is done after an update. 2 5 4 16 2 10 20 7 14 15 Figure 1: An α-balanced tree (which is a subtree of a larger tree) with α = 2/3. For example, consider the node containing 5. The total number of nodes in the subtree is 9. The left subtree has 2 nodes, so we have 2/9 ≤ 2/3. The right subtree has 6 nodes, so we have 6/9 ≤ 2/3. 3.1 The Rebalancing Operation Suppose x is some node in a BST, and that the subtree rooted at x has k nodes. The rebalancing operation rearranges the structure of a subtree rooted at x so that it has the same keys, but its height is at most log2 k. Rebalancing can be done using an inorder traversal of the subtree rooted at x. As we traverse the tree, we put the nodes, in order, into an array or ArrayList. The midpoint of the array will be the root of the new subtree, where as usual the midpoint is (first + last)/2. All the elements to the left of the midpoint will go into its left child, and all the elements to the right of the midpoint go into the right child. An example is shown in Figure 2. Perhaps the most natural way to construct the tree is to use recursion, as shown in Figure 3. Notes • Rebalancing a subtree is a purely structural operation that rearranges the links among existing nodes. You should not create any new nodes and you should not have to perform any key comparisons when rebalancing. • Rebalancing a subtree of size k should take O(k) time. • The operation may be performed on a subtree, so do not forget to update its parent if necessary. 3.2 Restoring Balance after Updates After we update a tree, we must check whether it remains α-balanced. If so, nothing more needs to be done. Otherwise, we must rebalance the tree. To be able to detect quickly whether the balance 3 2 4 5 7 10 12 14 15 16 20 20 10 4 15 2 5 7 12 14 16 5 4 16 2 10 20 7 14 12 15 Saturday, April 6, 2013 Figure 2: Rebalancing a subtree. conditions —inequalities (1) and (2)— are violated, we maintain for each node a count of the number of elements in that node’s subtree; note that this count includes the node itself. Whenever a node is added or removed, we need to iterate up the tree along the path to the root, starting with the node’s parent, updating the node counts. We also need to check whether any nodes along the path have become unbalanced, and identify the highest unbalanced node (if any) along that path. The rebalance operation should be performed on the node closest to the root. Figure 4 illustrates a tree with 31 elements prior to the addition of key 12. Using a value of α = 2/3, the tree is initially balanced. After 12 is added, two of the nodes along the path to the root become unbalanced: the nodes containing 5 and 16, respectively. We rebalance at the node containing 5, since it is the node closest to the root. 4 Task 1: ABTreeSet (120 Points) Your first task is to implement the class ABTreeSet, which extends Java’s AbstractSet abstract class, using α-balanced trees. The ABTreeSet class implements a set of elements with a natural ordering. Duplicate elements are not allowed. We also disallow null elements; any attempt to add a null element should result in a NullPointerException. The ABTreeSet class has the following signature. public class ABTreeSet < E extends Comparable <? super E > > extends AbstractSet The starting point for your implementation should be the sample code in ABTreeSet.java provided along with this assignment. ABTreeSet has methods in place to provide a public, read4 2 4 5 7 10 12 14 15 16 20 10 4 15 first mid last 2 4 5 7 12 14 15 16 20 5 7 5 7 7 12 14 12 14 14 20 16 16 20 20 2 2 (empty) (empty) (empty) Saturday, April 6, 2013 Figure 3: Recursive decomposition. 5 4 16 2 10 20 7 14 12 15 5 Unbalanced (7/10 > 2/3) Unbalanced (5/7 > 2/3) Added node -5 5 nodes 15 nodes 29 Figure 4: Adding key 12 to a balanced tree, using α = 2/3. The node containing 5 is the highest unbalanced node. 6 only view of the tree structure, and a public rebalance() method, which should implement the rebalancing operation described in Section 3.1. To avoid any problems with floating point arithmetic that could arise from using Inequalities (1) and (2), we represent α using two integer instance variables top and bottom that give its numerator and denominator; i.e., α = top/bottom. Then, Inequalities (1) and (2) are expressed as (number of elements in x’s left subtree) · bottom ≤ size · top, (3) and (number of elements in x’s right subtree) · bottom ≤ size · top. (4) The default value should be top = 2 and bottom = 3 (i.e., α = 2/3). The public interface BSTNode, provided with this assignment, defines the following readonly accessors for a node in a binary search tree (see the javadoc for details): BSTNode left(); BSTNode right(); BSTNode parent(); int count(); E data(); The left(), right(), parent(), and data() methods are self-explanatory. The count() method should return the total number of elements in the subtree rooted at that node. This method is needed to determine which, if any, nodes have become unbalanced as a result of an update, and is used to find the root of the subtree at which the rebalance operation must be applied (see Section 3.2). The method can be implemented by maintaining the size of the entire subtree, or by separately maintaining the sizes of the left and right subtrees. In any case, we require that the count() method run in constant time. ABTreeSet has an inner class Node that implements the BSTNode interface. You can make any modifications you wish to the inner class Node, provided that the class continues to conform to the BSTNode interface. The class ABTreeSet has two additional public methods: BSTNode root() Return the root of the tree. void rebalance(BSTNode bstNode) Perform a rebalance operation on the subtree rooted at the given node. There are three constructors. 7 public ABTreeSet() Default constructor. Builds a non-self-balancing tree. public ABTreeSet(boolean isSelfBalancing) If isSelfBalancing is true, builds a self-balancing tree with the default value α = 2/3. If isSelfBalancing is false, builds a non-self-balancing tree. public ABTreeSet(boolean isSelfBalancing, int top, int bottom) If isSelfBalancing is true, builds a self-balancing tree with α = top/bottom. If isSelfBalancing is false, builds a non-self-balancing tree (top and bottom are ignored). Throws an IllegalArgumentException if top/bottom is not strictly greater than 1/2 and strictly less than 1. ABTreeSet must override add(), contains(), remove(), size(), and iterator(). You must also override toString(), to display the current configuration of the underlying α-balanced for the set. This should be done according to the following rules: • Every node of the tree occupies a separate line with only its data on it. • The data stored at a node at depth d is printed with indentation 4d (i.e., preceded by 4d blanks). • Start at the root (at depth 0) and display the nodes in a preorder traversal. More specifically, suppose a node x is shown at line `. Then, starting at line ` + 1, – recursively print all nodes in the left subtree (if any) of x; – recursively print all nodes in the right subtree (if any) of x. • If a node has a left child but no right child, print its right child as null. • If a node has a right child but no left child, print its left child as null. • If a node is a leaf, print it with no further recursion. Figure 5 shows an α-balanced tree with 12 nodes, where α = 2/3. Figure 6 shows the output that should be generated by calling the toString() and System.out.println(). Summary. Your main tasks are as follows. 1. Implement a rebalance() operation for ABTreeSet. 2. Modify the Node class and the add(), remove(), and Iterator.remove() methods to maintain counts at each node. The count() method must be O(1). 3. Modify the add(), remove(), and Iterator.remove() methods so that, if the tree is constructed with the isSelfBalancing flag true, the tree is self-balancing. That is, if an operation causes any node to become unbalanced, a rebalance is automatically performed on the highest unbalanced node (which will always be somewhere along the path to the root). 8 30 55 53 60 62 35 31 37 25 20 10 50 Figure 5: An α-balanced tree, where α = 2/3. 50 30 25 10 null 20 null 35 31 37 55 53 60 null 62 Figure 6: The result of toString() for the tree of Figure 5. 9 Observe that items (1) and (2) can be done independently. Note the following. • The tree should maintain correct node counts whether or not it is self-balancing. • Any subtree can be explicitly rebalanced using the rebalance() method, whether or not the tree is self-balancing. 5 Task 2: ABTreeMap (50 Points) Your second task is to implement the ABTreeMap class, which uses an α-balanced tree to implement a mapping between a set of keys with a natural ordering and a collection of values. Duplicate key values are not allowed. We also disallow null keys or values; any attempt to add a null key or value should result in a NullPointerException. The ABTreeMap class has the following signature. public class ABTreeMap < K extends Comparable <? super K > , V > ABTreeMap has three constructors. public ABTreeMap() Default constructor. Builds a map that uses a non-self-balancing tree. public ABTreeMap(boolean isSelfBalancing) If isSelfBalancing is true, builds a map that uses self-balancing tree with the default value α = 2/3. If isSelfBalancing is false, builds a map that uses a non-self-balancing tree. public ABTreeMap(boolean isSelfBalancing, int top, int bottom) If isSelfBalancing is true, builds a map that uses a self-balancing tree with α = top/bottom. If isSelfBalancing is false, builds a map that uses a non-selfbalancing tree (top and bottom are ignored). Throws an IllegalArgumentException if top/bottom is not strictly greater than 1/2 and strictly less than 1. ABTreeMap has the following methods. public V put(K key, V value) Associates value with key in this map. Returns the previous value associated with key, or null if there was no mapping for key. public V get(K key) Returns the value to which key is mapped, or null if this map contains no mapping for key. 10 public V remove(K key) Removes the mapping for key from this map if it is present. Returns the previous value associated with key, or null if there was no mapping for key. public boolean containsKey(K key) Returns true if this map contains a mapping for key; otherwise, it returns false. public int size() Returns the number of key-value mappings in this map. public ABTreeSet keySet() Returns an ABTreeSet storing the keys (not the values) contained in this map. The tree structure of the ABTreeSet should be the same a the tree structure of this ABTreeMap. Example. Suppose this map consists of the following (key, value) pairs: (10, Carol), (21, Bill), (45, Carol),(81, Alice),(95, Bill). Then, the ABTreeSet returned should consist of 10, 21, 45, 81, 91. public ArrayList values() Returns an ArrayList storing the values contained in this map. Note that there may be duplicate values. The ArrayList should contain the values in ascending order of their corresponding keys. Example. Suppose this map consists of the following (key, value) pairs: (10, Carol), (21, Bill), (45, Carol),(81, Alice),(95, Bill). Then, the ArrayList returned should consist of the strings Carol, Bill, Carol, Alice, Bill, in that order. Note. Both keySet() and values() should be implemented by iterating through the ABTreeSet that represents the map. 6 Submission Write your classes in the edu.iastate.cs228.hw5 package. Turn in the zip file, not your class files. Please follow the guidelines posted under Documents & Links on Blackboard Learn. Also, follow project clarifications on Blackboard. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW5.zip. 11
