代写α-Balanced Trees，这个树是这门课自定义的一种树，非常变态。
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.
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.
Balanced Trees
Let T be a binary search tree and let be a constant. Let α 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)
(number of elements in x's right subtree) ≤ α·size, (2)
We say the tree T is α-balanced if every node is α-balanced.
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 k n, 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 21 α-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.
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.
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
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.
Task 1: ABTreeSet
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.
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)
(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 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.
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 l. Then, starting at line l + 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.
- Implement a rebalance() operation for ABTreeSet.
- 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).
- 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).
Task 2: ABTreeMap
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.
ABTreeMap has three constructors.1
public ABTreeMap()
Default constructor. Builds a map that uses a non-self-balancing tree.1
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.1
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.1
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.1
public V get(K key)
Returns the value to which key is mapped, or null if this map contains no mapping for key.1
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.1
public boolean containsKey(K key)
Returns true if this map contains a mapping for key; otherwise, it returns false.1
public int size()
Returns the number of key-value mappings in this map.1
public ABTreeSet<K> 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.1
public ArrayList<V> 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.
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.