Please provide the code in java for the following problem. Now that we are famil

Question

Please provide the code in java for the following problem.

Now that we are familiar with ‘maps’ and the Map interface, develop a program that uses the ‘java.util.TreeMap’ class to create a map that implements a Red-Black tree. Since it’s a Map, you will want to define K, V pairs. As class ‘K’, I want you to use the class you developed when working with Priority Queues – Auto, House, Book, Guitar, etc. For this lab, you will need to define a ‘Comparator’ class that overrides the method ‘compare’. This is what will be used by the TreeMap class to order entries. At a minimum, you need to create two files. One will be the ‘program’ that defines the ‘main ()’ method. In this file, you can define the ‘inner’ Comparator class that compares Houses’s, Auto’s, Book’s, Guitar’s or whatever using a method named ‘compare’.

In main ():

Create the TreeMap and then place a number of K, V pairs in the map. Again, the key will be a/an Auto, Boat, House, Book, etc. object. The value most simply could be a simple string.

Print out the map.

Then, put a new K, V pair into the map with a key identical to one used before. As before, this will be an object of type Auto, House, Boat, Book or whatever with a new string value.

Print out the map again, identifying this as a print-out after replacement of a value.

The constructor that you call for your TreeMap object will use ‘weird’ syntax. Between the online files (above) and the set of Eclipse ‘tips’ you should be able to figure out not only how to ‘type’ your TreeMap, but also how to supply it with a Comparator object. The second file will be the class defining Auto’s, Book’s, Boat’s, House’s or whatever that we created earlier.

Explanation / Answer

public class RedBlackBST<Key extends Comparable<Key>, Value> {

private static final boolean RED = true;
private static final boolean BLACK = false;

private Node root;

private class Node
{
private Key k;
private Value val;
private Node left, right;   
private boolean color;
private int N;   

public Node(Key k , Value val, boolean color, int N) {
this.k= k ;
this.val = val;
this.color = color;
this.N = N;
}
}

  

public RedBlackBST() {
}

private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}

private int size(Node x) {
if (x == null) return 0;
return x.N;
}

public int size() {
return size(root);
}

public boolean isEmpty() {
return root == null;
}

public Value get(Key k ) {
if (k == null) throw new NullPointerException("argument to get() is null");
return get(root, k );
}

private Value get(Node x, Key k ) {
while (x != null) {
int cmp = k .compareTo(x.k );
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else return x.val;
}
return null;
}

public boolean contains(Key k ) {
return get(k ) != null;
}

public void put(Key k , Value val) {
if (k == null) throw new NullPointerException("first argument to put() is null");
if (val == null) {
delete(k );
return;
}

root = put(root, k , val);
root.color = BLACK;

}

  
private Node put(Node h, Key k , Value val) {
if (h == null) return new Node(k , val, RED, 1);

int cmp = k .compareTo(h.k );
if (cmp < 0) h.left = put(h.left, k , val);
else if (cmp > 0) h.right = put(h.right, k , val);
else h.val = val;

if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;

return h;
}

public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("BST underflow");

if (!isRed(root.left) && !isRed(root.right))
root.color = RED;

root = deleteMin(root);
if (!isEmpty()) root.color = BLACK;

}

private Node deleteMin(Node h) {
if (h.left == null)
return null;

if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);

h.left = deleteMin(h.left);
return balance(h);
}

  
public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("BST underflow");

if (!isRed(root.left) && !isRed(root.right))
root.color = RED;

root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;

}

private Node deleteMax(Node h) {
if (isRed(h.left))
h = rotateRight(h);

if (h.right == null)
return null;

if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);

h.right = deleteMax(h.right);

return balance(h);
}

  
public void delete(Key k ) {
if (k == null) throw new NullPointerException("argument to delete() is null");
if (!contains(k )) return;

  
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;

root = delete(root, k );
if (!isEmpty()) root.color = BLACK;

}

private Node delete(Node h, Key k ) {

if (k .compareTo(h.k ) < 0) {
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, k );
}
else {
if (isRed(h.left))
h = rotateRight(h);
if (k .compareTo(h.k ) == 0 && (h.right == null))
return null;
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
if (key.compareTo(h.k ) == 0) {
Node x = min(h.right);
h.k = x.k ;
h.val = x.val;


h.right = deleteMin(h.right);
}
else h.right = delete(h.right, k );
}
return balance(h);
}

  
private Node rotateRight(Node h) {

Node x = h.left;
h.left = x.right;
x.right = h;
x.color = x.right.color;
x.right.color = RED;
x.N = h.N;
h.N = size(h.left) + size(h.right) + 1;
return x;
}

private Node rotateLeft(Node h) {

Node x = h.right;
h.right = x.left;
x.left = h;
x.color = x.left.color;
x.left.color = RED;
x.N = h.N;
h.N = size(h.left) + size(h.right) + 1;
return x;
}

private void flipColors(Node h) {

h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}

private Node moveRedLeft(Node h) {
  
flipColors(h);
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}

private Node moveRedRight(Node h) {
  
flipColors(h);
if (isRed(h.left.left)) {
h = rotateRight(h);
flipColors(h);
}
return h;
}

private Node balance(Node h) {
  
if (isRed(h.right)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);

h.N = size(h.left) + size(h.right) + 1;
return h;
}

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));
}

public Key min() {
if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
return min(root).k ;
}

// the smallest key in subtree rooted at x; null if no such key
private Node min(Node x) {
// assert x != null;
if (x.left == null) return x;
else return min(x.left);
}

public Key max() {
if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
return max(root).k ;
}

  
private Node max(Node x) {

if (x.right == null) return x;
else return max(x.right);
}

public Key floor(Key k ) {
if (k == null) throw new NullPointerException("argument to floor() is null");
if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
Node x = floor(root, k );
if (x == null) return null;
else return x.k ;
}

private Node floor(Node x, Key k ) {
if (x == null) return null;
int cmp = k .compareTo(x.k );
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, k );
Node t = floor(x.right, k );
if (t != null) return t;
else return x;
}

  
public Key ceiling(Key k ) {
if (k == null) throw new NullPointerException("argument to ceiling() is null");
if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
Node x = ceiling(root, k );
if (x == null) return null;
else return x.k ;
}

private Node ceiling(Node x, Key k ) {
if (x == null) return null;
int cmp = k .compareTo(x.k );
if (cmp == 0) return x;
if (cmp > 0) return ceiling(x.right, k );
Node t = ceiling(x.left, k );
if (t != null) return t;
else return x;
}

public Key select(int p) {
if (p < 0 || p >= size()) throw new IllegalArgumentException();
Node x = select(root, p);
return x.k ;
}

private Node select(Node x, int p) {
  
int t = size(x.left);
if (t > p) return select(x.left, p);
else if (t < p) return select(x.right, p-t-1);
else return x;
}

  
public int rank(Key k ) {
if (k == null) throw new NullPointerException("argument to rank() is null");
return rank(k , root);
}

  
private int rank(Key k , Node x) {
if (x == null) return 0;
int cmp = k .compareTo(x.k );
if (cmp < 0) return rank(k , x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(k , x.right);
else return size(x.left);
}

public Iterable<Key> ks() {
if (isEmpty()) return new Queue<Key>();
return ks(min(), max());
}

  
public Iterable<Key> ks(Key lo, Key hi) {
if (lo == null) throw new NullPointerException("first argument to ks() is null");
if (hi == null) throw new NullPointerException("second argument to ks() is null");

Queue<Key> queue = new Queue<Key>();
  
keys(root, queue, lo, hi);
return queue;
}

private void ks(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) return;
int cmplo = lo.compareTo(x.k );
int cmphi = hi.compareTo(x.k );
if (cmplo < 0) ks(x.left, queue, lo, hi);
if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.k );
if (cmphi > 0) ks(x.right, queue, lo, hi);
}

public int size(Key lo, Key hi) {
if (lo == null) throw new NullPointerException("first argument to size() is null");
if (hi == null) throw new NullPointerException("second argument to size() is null");

if (lo.compareTo(hi) > 0) return 0;
if (contains(hi)) return rank(hi) - rank(lo) + 1;
else return rank(hi) - rank(lo);
}

  
private boolean check() {
if (!isBST()) StdOut.println("Not in symmetric order");
if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
if (!isRankConsistent()) StdOut.println("Ranks not consistent");
if (!is23()) StdOut.println("Not a 2-3 tree");
if (!isBalanced()) StdOut.println("Not balanced");
return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
}

  
private boolean isBST() {
return isBST(root, null, null);
}

private boolean isBST(Node x, Key min, Key max) {
if (x == null) return true;
if (min != null && x.k .compareTo(min) <= 0) return false;
if (max != null && x.k .compareTo(max) >= 0) return false;
return isBST(x.left, min, x.k ) && isBST(x.right, x.k , max);
}

  
private boolean isSizeConsistent() { return isSizeConsistent(root); }
private boolean isSizeConsistent(Node x) {
if (x == null) return true;
if (x.N != size(x.left) + size(x.right) + 1) return false;
return isSizeConsistent(x.left) && isSizeConsistent(x.right);
}

private boolean isRankConsistent() {
for (int i = 0; i < size(); i++)
if (i != rank(select(i))) return false;
for (Key k : ks())
if (k .compareTo(select(rank(k))) != 0) return false;
return true;
}

  
private boolean is23() { return is23(root); }
private boolean is23(Node x) {
if (x == null) return true;
if (isRed(x.right)) return false;
if (x != root && isRed(x) && isRed(x.left))
return false;
return is23(x.left) && is23(x.right);
}

  
private boolean isBalanced() {
int black = 0;   
Node x = root;
while (x != null) {
if (!isRed(x)) black++;
x = x.left;
}
return isBalanced(root, black);
}

private boolean isBalanced(Node x, int black) {
if (x == null) return black == 0;
if (!isRed(x)) black--;
return isBalanced(x.left, black) && isBalanced(x.right, black);
}

public static void main(String[] args) {
RedBlackBST<String, Integer> st = new RedBlackBST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String k = StdIn.readString();
st.put(k , i);
}
for (String s : st.ks())
StdOut.println(s + " " + st.get(s));
StdOut.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.