JAVA

Write a reference class called A4ReorganizingBST. The trees of this class will rebalance themselves after a certain number of changes to the tree, rather than after every change, as is done by AVL trees and LLRB trees. The class will implement the following API:

public A4ReorganizingBST()

public V get(K key)

public void put(K key, V value)

public void delete(K key)

public int height()

Copy the code for the constructor and the next three methods (and their private counterparts) from the SimplerBST class (for reference below). You will then modify the put and delete methods. What will make this tree a reorganizing tree is that, after every 100 changes (that is, puts or deletes), your code will rebuild the tree from scratch and insert the keys in such a way that the new tree is balanced. You will need an instance variable to count the changes. Modify the public put and delete methods so that they increment this counter and, after calling their respective private methods, check the value of the counter. If it is greater than or equal to 100, the call the method described next.

Write a private void method rebuildTree that takes no parameters. This will:

Reset the change counter to 0

Build an array of the keys

Sort the array

Call the next method described below to get a queue of the keys in median order

Declare a Node variable; this will be the root of the new and balanced tree

Iterate through the queue returned by that method and call the public put, passing it the root of the new tree

Change the root instance variable to refer to this new root

Write a private method called MedianOrder that takes as its only parameter a sorted array of the keys and that returns a queue of keys. In that method:

Create three queues: median queue, left index queue, right index queue; the first one will hold keys, the other two will hold integer indices enqueue 0 onto the left index queue and the length of the array minus one on the right index queue while the left index queue is not empty: let left be the dequeue of the left index queue and right the same for the right index queue if left <= right then let median index by the average of left and right enqueue the key in the array at the median index onto the median queue enqueue left and the median index minus one onto the left index queue enqueue right and the median index plus one onto the right index queue end if end while return the median queue

Use the algs13.Queue class (see below) to create the queues. Use the test program A4TestReorganizingBST (see below) to test your class.

--------------------------------------------------------------------------

SimplerBST class

package week1examples;

/*

* This is a simplified version of the BST class

* from the algs32 package.

*

*/

import stdlib.*;

import algs13.Queue;

public class SimplerBST, V> {

private Node root; // root of BST

private static class Node,V> {

public K key; // sorted by key

public V val; // associated data

public Node left, right; // left and right subtrees

public Node(K key, V val) {

this.key = key;

this.val = val;

}

}

public SimplerBST() {}

/* *********************************************************************

* Search BST for given key, and return associated value if found,

* return null if not found

***********************************************************************/

// does there exist a key-value pair with given key?

public boolean contains(K key) {

return get(key) != null;

}

// return value associated with the given key, or null if no such key exists

public V get(K key) { return get(root, key); }

private V get(Node x, K key) {

if (x == null) return null;

int cmp = key.compareTo(x.key);

if (cmp < 0) return get(x.left, key);

else if (cmp > 0) return get(x.right, key);

else return x.val;

}

/* *********************************************************************

* Insert key-value pair into BST

* If key already exists, update with new value

***********************************************************************/

public void put(K key, V val) {

if (val == null) { delete(key); return; }

root = put(root, key, val);

}

private Node put(Node x, K key, V val) {

if (x == null) return new Node<>(key, val);

int cmp = key.compareTo(x.key);

if (cmp < 0)

x.left = put(x.left, key, val);

else if (cmp > 0)

x.right = put(x.right, key, val);

else

x.val = val;

return x;

}

/* *********************************************************************

* Delete

***********************************************************************/

public void delete(K key) {

root = delete(root, key);

}

private Node delete(Node x, K key) {

if (x == null) return null;

int cmp = key.compareTo(x.key);

if (cmp < 0) x.left = delete(x.left, key);

else if (cmp > 0) x.right = delete(x.right, key);

else {

// x is the node to be deleted.

// The value returned in each of these cases below

// becomes the value of the child reference from

// the parent of x. Returning a null makes that

// reference a null and so cuts x off, causing its

// automatic deletion.

// Determine how many children x has.

if (x.right == null && x.left == null){

// This is a leaf node.

return null;

} else if (x.right == null) {

// One child, to the left.

return x.left;

} else if (x.left == null) {

// One child, to the right.

return x.right;

} else {

// Node x has two children.

// Find the node in x's right subtree with

// the minimum key.

Node rightTreeMinNode = findMin(x.right);

x.key = rightTreeMinNode.key;

x.val = rightTreeMinNode.val;

x.right = delete(x.right, rightTreeMinNode.key);

}

}

return x;

}

private Node findMin(Node x) {

if (x.left == null) return x;

else return findMin(x.left);

}

public void printKeys() {

printKeys(root);

}

private void printKeys(Node x) {

if (x == null) return;

printKeys(x.left);

StdOut.println(x.key);

printKeys(x.right);

}

public Iterable keys() {

Queue q = new Queue<>();

inOrder(root, q);

return q;

}

private void inOrder(Node x, Queue q) {

if (x == null) return;

inOrder(x.left, q);

q.enqueue(x.key);

inOrder(x.right, q);

}

public int height() {

return height(root);

}

private int height(Node x) {

if (x == null) return -1;

return 1+Math.max(height(x.left), height(x.right));

}

/* ***************************************************************************

* Visualization

*****************************************************************************/

public void drawTree() {

if (root != null) {

StdDraw.setPenColor (StdDraw.BLACK);

StdDraw.setCanvasSize(1200,700);

drawTree(root, .5, 1, .25, 0);

}

}

private void drawTree (Node n, double x, double y, double range, int depth) {

int CUTOFF = 10;

StdDraw.text (x, y, n.key.toString ());

StdDraw.setPenRadius (.007);

if (n.left != null && depth != CUTOFF) {

StdDraw.line (x-range, y-.08, x-.01, y-.01);

drawTree (n.left, x-range, y-.1, range*.5, depth+1);

}

if (n.right != null && depth != CUTOFF) {

StdDraw.line (x+range, y-.08, x+.01, y-.01);

drawTree (n.right, x+range, y-.1, range*.5, depth+1);

}

}

}

----------------------------------------------------------------------

Queue Class

package algs13;

import stdlib.*;

import java.util.Iterator;

import java.util.NoSuchElementException;

/* ***********************************************************************

* Compilation: javac Queue.java

* Execution: java Queue < input.txt

* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt

*

* A generic queue, implemented using a linked list.

*

* % java Queue < tobe.txt

* to be or not to be (2 left on queue)

*

*************************************************************************/

/**

* The Queue class represents a first-in-first-out (FIFO)

* queue of generic items.

* It supports the usual enqueue and dequeue

* operations, along with methods for peeking at the top item,

* testing if the queue is empty, and iterating through

* the items in FIFO order.

*

* All queue operations except iteration are constant time.

*

* For additional documentation, see Section 1.3 of

* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Queue implements Iterable {

private int N; // number of elements on queue

private Node first; // beginning of queue

private Node last; // end of queue

// helper linked list class

private static class Node {

public Node() { }

public T item;

public Node next;

}

/**

* Create an empty queue.

*/

public Queue() {

first = null;

last = null;

N = 0;

}

/**

* Is the queue empty?

*/

public boolean isEmpty() {

return first == null;

}

/**

* Return the number of items in the queue.

*/

public int size() {

return N;

}

/**

* Return the item least recently added to the queue.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T peek() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

return first.item;

}

/**

* Add the item to the queue.

*/

public void enqueue(T item) {

Node oldlast = last;

last = new Node<>();

last.item = item;

last.next = null;

if (isEmpty()) first = last;

else oldlast.next = last;

N++;

}

/**

* Remove and return the item on the queue least recently added.

* @throws java.util.NoSuchElementException if queue is empty.

*/

public T dequeue() {

if (isEmpty()) throw new NoSuchElementException("Queue underflow");

T item = first.item;

first = first.next;

N--;

if (isEmpty()) last = null;

return item;

}

/**

* Return string representation.

*/

public String toString() {

StringBuilder s = new StringBuilder();

for (T item : this)

s.append(item + " ");

return s.toString();

}

// check internal invariants

private static boolean check(Queue that) {

int N = that.N;

Queue.Node first = that.first;

Queue.Node last = that.last;

if (N == 0) {

if (first != null) return false;

if (last != null) return false;

}

else if (N == 1) {

if (first == null || last == null) return false;

if (first != last) return false;

if (first.next != null) return false;

}

else {

if (first == last) return false;

if (first.next == null) return false;

if (last.next != null) return false;

// check internal consistency of instance variable N

int numberOfNodes = 0;

for (Queue.Node x = first; x != null; x = x.next) {

numberOfNodes++;

}

if (numberOfNodes != N) return false;

// check internal consistency of instance variable last

Queue.Node lastNode = first;

while (lastNode.next != null) {

lastNode = lastNode.next;

}

if (last != lastNode) return false;

}

return true;

}

/**

* Return an iterator that iterates over the items on the queue in FIFO order.

*/

public Iterator iterator() {

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator {

private Node current = first;

public boolean hasNext() { return current != null; }

public void remove() { throw new UnsupportedOperationException(); }

public T next() {

if (!hasNext()) throw new NoSuchElementException();

T item = current.item;

current = current.next;

return item;

}

}

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

toGraphviz (gb, null, first);

gb.toFile (filename, "rankdir=\"LR\"");

}

private void toGraphviz (GraphvizBuilder gb, Node prev, Node n) {

if (n == null) { gb.addNullEdge (prev); return; }

gb.addLabeledNode (n, n.item.toString ());

if (prev != null) gb.addEdge (prev, n);

toGraphviz (gb, n, n.next);

}

/**

* A test client.

*/

public static void main(String[] args) {

StdIn.fromString ("to be or not to - be - - that - - - is");

Queue q = new Queue<>();

int count = 0;

q.toGraphviz ("queue" + count + ".png"); count++;

while (!StdIn.isEmpty()) {

String item = StdIn.readString();

if (!item.equals("-")) q.enqueue(item);

else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");

q.toGraphviz ("queue" + count + ".png"); count++;

}

StdOut.println("(" + q.size() + " left on queue)");

}

}

------------------------------------------------------------------------------------------------------------

A4TestReorganizingBST

package csc403;

import java.util.Arrays;

import stdlib.*;

import week1examples.*;

import week3examples.*;

public class A4TestReorganizingBST {

public static void main(String[] args) {

StdIn.fromFile("data/tale.txt");

String[] words = StdIn.readAllStrings();

SimplerBST bst = new SimplerBST<>();

A4ReorganizingBST robst = new A4ReorganizingBST<>();

AVLTreeST avl = new AVLTreeST<>();

Stopwatch timer;

StdOut.println("=== Times for words as they appear in the text ===");

// Fill and time the usual BST.

timer = new Stopwatch();

for (String word: words) {

bst.put(word, true);

}

StdOut.println(" Elapsed time for usual BST: " + timer.elapsedTime());

StdOut.println("Height of BST: " + bst.height());

// Fill and time the reorganizing BST.

timer = new Stopwatch();

for (String word: words) {

robst.put(word, true);

}

StdOut.println(" Elapsed time for reorganizing tree: " + timer.elapsedTime());

StdOut.println("Height of reorganized tree: " + robst.height());

// Fill and time the AVL tree.

timer = new Stopwatch();

for (String word: words) {

avl.put(word, true);

}

StdOut.println(" Elapsed time for AVL tree: " + timer.elapsedTime());

StdOut.println("Height of AVL tree: " + avl.height());

StdOut.println(" === Times for sorted words ===");

bst = new SimplerBST<>();

robst = new A4ReorganizingBST<>();

avl = new AVLTreeST<>();

Arrays.sort(words);

// Fill and time the usual BST.

timer = new Stopwatch();

for (String word: words) {

bst.put(word, true);

}

StdOut.println(" Elapsed time for usual BST: " + timer.elapsedTime());

StdOut.println("Height of BST: " + bst.height());

// Fill and time the reorganizing BST.

timer = new Stopwatch();

for (String word: words) {

robst.put(word, true);

}

StdOut.println(" Elapsed time for reorganizing tree: " + timer.elapsedTime());

StdOut.println("Height of reorganized tree: " + robst.height());

// Fill and time the AVL tree.

timer = new Stopwatch();

for (String word: words) {

avl.put(word, true);

}

StdOut.println(" Elapsed time for AVL tree: " + timer.elapsedTime());

StdOut.println("Height of AVL tree: " + avl.height());

}

}