Java

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

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

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

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

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

*

* A generic queue, implemented using a linked list.

*

* % java Queue

* 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());

}

}

will write a reference class called AAReorganiz ngBST. The idea is that trees of this class will rebalance themselves after a certain n nber of tree, rather than after every change, as is done by AVL trees and LLRB trees. The class will implement the following AP , public AAReorganizingBSTO 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 cdlass in the week 1 examples package. You wll then modily 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 vold 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 list InMedianOrder 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 enpty let left be the dequeue of the left index queue and right the sane for the right index queue if left ce 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 to test your class Use the algs13.Queue class to create the queues. Use the test program AM will write a reference class called AAReorganiz ngBST. The idea is that trees of this class will rebalance themselves after a certain n nber of tree, rather than after every change, as is done by AVL trees and LLRB trees. The class will implement the following AP , public AAReorganizingBSTO 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 cdlass in the week 1 examples package. You wll then modily 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 vold 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 list InMedianOrder 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 enpty let left be the dequeue of the left index queue and right the sane for the right index queue if left ce 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 to test your class Use the algs13.Queue class to create the queues. Use the test program AM