Suppose x is some node in a BST, and that the subtree rooted at x has k nodes. T
ID: 3534643 • Letter: S
Question
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 . Perhaps the most natural
way to construct the tree is to use recursion, as shown in Figure .
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.
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 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.
@To summarize, main tasks are as follows.
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).
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).
Below is my code :
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<E> inorderArray = new ArrayList<E>();
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;
//System.out.println("This is the inorder array list: ");
if(node!= null){
inOrder(current.left);
inorderArray.add(node.data());
//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)
{
//TODO
}
/**
* Returns a read-only view of the root node of this tree.
* @return root node of this tree
*/
public BSTNode<E> root()
{
return root;
}
/**
* Performs a rebalance 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 rebalanced.
* @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
reBalancedNode(inorderArray, 0,inorderArray.size()-1);
}
@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;
}
}
}
Explanation / Answer
more time