1. Implement a rebalance() operation for BalancedBSTSet. 2. Modify the Node clas
ID: 3534699 • Letter: 1
Question
1. Implement a rebalance() operation for BalancedBSTSet.
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).
I have finished the rebalance() method but it doesn't work when I try to print it.
Also, I need to modify the count() so it will know when to rebalanced
Here is my code below, ask any question if you need me to modify
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
*
* Binary search tree implementation of the Set interface. The contains() and
* remove() methods of AbstractSet are overridden to search the tree without
* using the iterator. Instances of this class always maintain node counts; that
* is, the count() method of the BSTNode interface is implemented to be O(1).
* If constructed with the isSelfBalancing flag true, instances of this tree are
* self-balancing: whenever an add(), remove(), or Iterator.remove() operation
* causes any node to become unbalanced, a re-balance operation is automatically
* performed at the highest unbalanced node.
*/
public class BalancedBSTSet<E extends Comparable<? super E>> extends AbstractSet<E>
{
/**
* Root of this tree.
*/
protected Node root;
/**
* Number of elements in this tree.
*/
protected int size;
/**
* Node type for this implementation.
*/
private ArrayList<Node> inorderArray = new ArrayList<Node>();
private boolean isSelfBalancing;
private int top;
private int bottom;
protected class Node implements BSTNode<E>
{
public Node left;
public Node right;
public Node parent;
public E data;
public Node(E key, Node parent)
{
this.data = key;
this.parent = parent;
}
@Override
public BSTNode<E> left()
{
return left;
}
@Override
public BSTNode<E> right()
{
return right;
}
@Override //TODO
public int count()
{
return size;
}
@Override
public E data()
{
return data;
}
@Override
public BSTNode<E> parent()
{
return parent;
}
@Override
public String toString()
{
return data.toString();
}
}
/**
* Constructs an empty binary search tree. This tree will maintain
* node counts but will not automatically perform rebalance operations.
*/
public BalancedBSTSet()
{
this(false);
}
/**
* Constructs an empty binary search tree. If the isSelfBalancing
* flag is true, the tree will be self-balancing: if so, whenever an add(),
* remove(), or Iterator.remove() operation causes any node to become
* unbalanced, a rebalance operation is automatically performed at the
* highest unbalanced node. The default value alpha = 2/3 is used for
* the balance condition. Maintains node counts whether or not
* isSelfBalancing is true.
*
* @param isSelfBalancing true if this binary search tree is
* to be self-balancing, false otherwise
*/
public BalancedBSTSet(boolean isSelfBalancing)
{
this(isSelfBalancing, 2, 3);
}
public void inOrder(BSTNode<E> node){
Node current = (Node) node;
if(node!= null){
inOrder(current.left);
inorderArray.add(current);
//System.out.print(node.data()+ " ");
inOrder(current.right);
}
}
/**
* Constructs an empty binary search tree. If the isSelfBalancing
* flag is true, the tree will be self-balancing: if so, whenever an add(),
* remove(), or Iterator.remove() operation causes any node to become
* unbalanced, a rebalance operation is automatically performed at the
* highest unbalanced node. The given alpha = top/bottom is used for
* the balance condition. Maintains node counts whether or not
* isSelfBalancing is true.
*
* @param isSelfBalancing true if this binary search tree is
* to be self-balancing, false otherwise
* @param top numerator of the fraction alpha
* @param bottom denominator of the fraction alpha
* @throws IllegalArgumentException if top / bottom is less than 1/2
*/
public BalancedBSTSet(boolean isSelfBalancing, int top, int bottom)
{
this.isSelfBalancing = isSelfBalancing;
this.top = top;
this.bottom = bottom;
if (((float)top)/bottom < 0.5)
throw new IllegalArgumentException("top / bottom is less than 1/2 ");
}
/**
* Returns a read-only view of the root node of this tree.
* @return root node of this tree
*/
public BSTNode<E> root()
{
return root;
}
/**
* Create binary search tree.
* @param array of elements
* @return The root of the tree.
*/
public Node makeTree(ArrayList<Node> list) {
int low = 0;
int high = list.size()-1;
return makeTree(low, high,list);
}
/**
* Re-constructor the tree.
* @param low The lowest array position.
* @param high The highest array position.
* @param array of elements
* @return The root of the tree.
*/
private Node makeTree(int low, int high, ArrayList<Node> list) {
if (low > high) {
return null;
}
else {
int mid = (low + high) / 2;
Node temp;
temp = list.get(mid);
temp.left = makeTree(low,mid-1,list); //left
temp.right = makeTree(mid+1,high,list);//right
}
return root;
}
/**
* Performs a re-balance operation on the given subtree. This operation
* does not create or destroy any nodes and does not change the size of
* this tree.
* @param bstNode root of the subtree to be re-balanced.
* @throws IllegalArgumentException if the given node is not part of this tree.
* @throws ClassCastException if the given node cannot be cast to the
* correct concrete node type for this tree.
*/
public void rebalance(BSTNode<E> bstNode)
{
inOrder(bstNode);// in-order traversal the node into the array list (in-order array)
//root = new Node(null,null); //empty all the tree
//makeTree(inorderArray);
makeTree(0, inorderArray.size()-1, inorderArray);
}
@Override
public boolean contains(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
return findEntry(key) != null;
}
@Override
public boolean add(E key)
{
if (root == null)
{
root = new Node(key, null);
++size;
return true;
}
Node current = root;
while (true)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
// key is already in the tree
return false;
}
else if (comp > 0)
{
if (current.left != null)
{
current = current.left;
}
else
{
current.left = new Node(key, current);
++size;
return true;
}
}
else
{
if (current.right != null)
{
current = current.right;
}
else
{
current.right = new Node(key, current);
++size;
return true;
}
}
}
}
@Override
public boolean remove(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
Node n = findEntry(key);
if (n == null)
{
return false;
}
unlinkNode(n);
return true;
}
/**
* Returns the node containing key, or null if the key is not
* found in the tree.
* @param key
* @return the node containing key, or null if not found
*/
protected Node findEntry(E key)
{
Node current = root;
while (current != null)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
return current;
}
else if (comp > 0)
{
current = current.left;
}
else
{
current = current.right;
}
}
return null;
}
/**
* Returns the successor of the given node.
* @param n
* @return the successor of the given node in this tree,
* or null if there is no successor
*/
protected Node successor(Node n)
{
if (n == null)
{
return null;
}
else if (n.right != null)
{
// leftmost entry in right subtree
Node current = n.right;
while (current.left != null)
{
current = current.left;
}
return current;
}
else
{
// we need to go up the tree to the closest ancestor that is
// a left child; its parent must be the successor
Node current = n.parent;
Node child = n;
while (current != null && current.right == child)
{
child = current;
current = current.parent;
}
// either current is null, or child is left child of current
return current;
}
}
/**
* Removes the given node, preserving the binary search
* tree property of the tree.
* @param n node to be removed
*/
protected void unlinkNode(Node n)
{
// first deal with the two-child case; copy
// data from successor up to n, and then delete successor
// node instead of given node n
if (n.left != null && n.right != null)
{
Node s = successor(n);
n.data = s.data;
n = s; // causes s to be deleted in code below
}
// n has at most one child
Node replacement = null;
if (n.left != null)
{
replacement = n.left;
}
else if (n.right != null)
{
replacement = n.right;
}
// link replacement into tree in place of node n
// (replacement may be null)
if (n.parent == null)
{
root = replacement;
}
else
{
if (n == n.parent.left)
{
n.parent.left = replacement;
}
else
{
n.parent.right = replacement;
}
}
if (replacement != null)
{
replacement.parent = n.parent;
}
--size;
}
@Override
public Iterator<E> iterator()
{
return new BSTIterator();
}
@Override
public int size()
{
return size;
}
/**
* Returns a representation of this tree as a multi-line string.
* The tree is drawn with the root at the left and children are
* shown top-to-bottom. Leaves are marked with a "-" and non-leaves
* are marked with a "+".
*/
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
toStringRec(root, sb, 0);
return sb.toString();
}
/**
* Preorder traversal of the tree that builds a string representation
* in the given StringBuilder.
* @param n root of subtree to be traversed
* @param sb StringBuilder in which to create a string representation
* @param depth depth of the given node in the tree
*/
private void toStringRec(Node n, StringBuilder sb, int depth)
{
for (int i = 0; i < depth; ++i)
{
sb.append(" ");
}
if (n == null)
{
sb.append("- ");
return;
}
if (n.left != null || n.right != null)
{
sb.append("+ ");
}
else
{
sb.append("- ");
}
sb.append(n.data.toString() + " (" + n.count() + ")");
sb.append(" ");
if (n.left != null || n.right != null)
{
toStringRec(n.left, sb, depth + 1);
toStringRec(n.right, sb, depth + 1);
}
}
/**
* Iterator implementation for this binary search tree. The elements
* are returned in ascending order according to their natural ordering.
*/
private class BSTIterator implements Iterator<E>
{
/**
* Node to be returned by next call to next().
*/
private Node current;
/**
* Node returned by last call to next() and available
* for removal. This field is null when no node is
* available to be removed.
*/
private Node pending;
/**
* Constructs an iterator starting at the smallest
* element in the tree.
*/
public BSTIterator()
{
// start out at smallest value
current = root;
if (current != null)
{
while (current.left != null)
{
current = current.left;
}
}
}
@Override
public boolean hasNext()
{
return current != null;
}
@Override
public E next()
{
if (!hasNext()) throw new NoSuchElementException();
pending = current;
current = successor(current);
return pending.data;
}
@Override
public void remove()
{
if (pending == null) throw new IllegalStateException();
// Remember, current points to the successor of
// pending, but if pending has two children, then
// unlinkNode(pending) will copy the successor's data
// into pending and delete the successor node.
// So in this case we want to end up with current
// pointing to the pending node.
if (pending.left != null && pending.right != null)
{
current = pending;
}
unlinkNode(pending);
pending = null;
}
}
public static void main(String[] args)
{
BalancedBSTSet<Integer> tree = new BalancedBSTSet<Integer>();
tree.add(7);
tree.add(2);
tree.add(4);
tree.add(5);
tree.add(10);
tree.add(12);
tree.add(20);
tree.add(14);
tree.add(16);
tree.add(15);
tree.rebalance(tree.root());
System.out.println(tree.toString());
}
}
Explanation / Answer
Need more time
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.