PLEASE DO NOT REPOST CODE FROM OTHER ANSWERS The task of this project is to impl
ID: 3728442 • Letter: P
Question
PLEASE DO NOT REPOST CODE FROM OTHER ANSWERS
The task of this project is to implement in Java a red-black tree data structure. However, the tree will be simplified – you only need to support insertion, not deletion.
Specification
The project must implement the following specification exactly, including all identifier names, method signatures, the presence or absence of exceptional behavior, etc. That being said, anything not clearly indicated by the UML diagram(s) or explicitly stated in the description is left up to your discretion. You may also add private helper methods or additional fields as necessary.
Structure
Note that a box with a dashed border over the top right of a class entity denotes a generic type parameter. In this case, the red-black tree class has a generic type named E that extends Comparable – you may choose whether or not to make Node generic as well. The Comparable interface is located in the java.lang package, so it is not necessary to import it. Finally, for this project you should locate your code in the default package.
Behavior
insert should insert the given element into the tree at the correct position, and then rebalance the tree if necessary. The correct position is defined by the properties of a binary search tree, and the rebalancing procedure should enforce the properties of a red-black tree. Regarding input validation, insert should immediately throw a NullPointerException with a descriptive message if the given element is null. Alternatively, if the given element is a duplicate of an element already in the tree, then insert should not insert the given element. The return value should indicate whether the given element was inserted into the tree or not.
Two elements are considered duplicates iff (if and only if) they compare equal to each other using the compareTo method. Likewise, the ordering of any two elements for the purposes of insertion and rebalancing is given by the same method.
contains should return whether the tree contains any element that compares equal to the given object using the compareTo method of the object. This means that you should always do object.compareTo(element) but never do element.compareTo(object).
However, if the given object is null, then contains should not throw an exception but rather should return false.
toString should override the eponymous method of Object and return a string representing the pre-order traversal of this tree. The returned string should be the ordered concatenation of invoking the toString method of each element in the traversal, where every two adjacent elements should be separated by a single space character (“ ”). If an element is located in a red node, then it should be preceded by a single asterisk character (“*”) in the output string. Otherwise, an element located in a black node should not be preceded by an asterisk. An example of the output is as follows (assuming that the elements are of type Integer):
30 2 *5 47 *60
It is entirely optional, but it may make your life easier to use a StringJoiner and/or to implement Node#toString() as well.
The color field of the node class should be assigned and evaluated using the RED and BLACK constants of the enclosing tree class. This means that you should always do color = BLACK or if(color == RED) but never do color = true or if(!color).
Main Class
Along with the RedBlackTree class include another class that has a main function. You can name this class anything just clearly indicate the name in Readme File. This class will take two command line arguments. The first argument will be the input file name and second will be output file name. The input file will be given to the program and the output file will be generated by the program. This main class will create an instance of RedBlackTree and do the operations specified in the input file. To understand the format of input and output files please see the following examples.
Example 2
Students
The corresponding correct output file should be
Only works for objects Integers and Strings Remember your
RedBlackTree class itself should be generic and should allow any object that is Comparable. We will be testing your RedBlackTree class separately using unit testing modules.
The specification for this project emulates several conventions used in the actual Java standard library (with appropriate simplifications). For example, the TreeSet class is a red-black tree that uses RED and BLACK boolean constants exactly as specified here in order to more efficiently simulate a binary enum without sacrificing the expressive power of an enum.
you may assume the input file will request to create RedBlackTree for either Integer Objects or String Objects. For all other objects you may generate an error message in the output file and quit.
Remember the RedBlackTree class itself should be generic and should allow to create trees of any object E that is Comparable<E> . We will be checking the RedBlackTree class without using the your Main class using unit testing routines.
E fextends Comparable) E {extends Comparable«E»): «staticx Node RedBlackTree «static»-RED: boolean = false «static»-BLACK: boolean = true -root: Node -element: E -leftChild: Node -rightChild: Node -parent: Node -color: boolean +insert(element: E): boolean [throws NullPointerException) contains(object: ComparablecE>): boolean +toString0: StringExplanation / Answer
package com.test;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
// BST helper node data type
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // links to left and right subtrees
private boolean color; // color of parent link
private int size; // subtree count
public Node(Key key, Value val, boolean color, int size) {
this.key = key;
this.val = val;
this.color = color;
this.size = size;
}
}
/**
* Initializes an empty symbol table.
*/
public RedBlackTree() {
}
/***************************************************************************
* Node helper methods.
***************************************************************************/
// is node x red; false if x is null ?
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
// number of node in subtree rooted at x; 0 if x is null
private int size(Node x) {
if (x == null) return 0;
return x.size;
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size() {
return size(root);
}
/**
* Is this symbol table empty?
* @return {@code true} if this symbol table is empty and {@code false} otherwise
*/
public boolean isEmpty() {
return root == null;
}
/***************************************************************************
* Standard BST search.
***************************************************************************/
/**
* Returns the value associated with the given key.
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and {@code null} if the key is not in the symbol table
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
return get(root, key);
}
// value associated with the given key in subtree rooted at x; null if no such key
private Value get(Node x, Key key) {
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else return x.val;
}
return null;
}
/**
* Does this symbol table contain the given key?
* @param key the key
* @return {@code true} if this symbol table contains {@code key} and
* {@code false} otherwise
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public boolean contains(Key key) {
return get(key) != null;
}
/***************************************************************************
* Red-black tree insertion.
***************************************************************************/
/**
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
* Deletes the specified key (and its associated value) from this symbol table
* if the specified value is {@code null}.
*
* @param key the key
* @param val the value
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
root = put(root, key, val);
root.color = BLACK;
// assert check();
}
// insert the key-value pair in the subtree rooted at h
private Node put(Node h, Key key, Value val) {
if (h == null) return new Node(key, val, RED, 1);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
// fix-up any right-leaning links
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.size = size(h.left) + size(h.right) + 1;
return h;
}
/***************************************************************************
* Red-black tree helper functions.
***************************************************************************/
// make a left-leaning link lean to the right
private Node rotateRight(Node h) {
// assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = x.right.color;
x.right.color = RED;
x.size = h.size;
h.size = size(h.left) + size(h.right) + 1;
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
// assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = x.left.color;
x.left.color = RED;
x.size = h.size;
h.size = size(h.left) + size(h.right) + 1;
return x;
}
// flip the colors of a node and its two children
private void flipColors(Node h) {
// h must have opposite color of its two children
// assert (h != null) && (h.left != null) && (h.right != null);
// assert (!isRed(h) && isRed(h.left) && isRed(h.right))
// || (isRed(h) && !isRed(h.left) && !isRed(h.right));
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
// Assuming that h is red and both h.left and h.left.left
// are black, make h.left or one of its children red.
private Node moveRedLeft(Node h) {
// assert (h != null);
// assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
flipColors(h);
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}
// Assuming that h is red and both h.right and h.right.left
// are black, make h.right or one of its children red.
private Node moveRedRight(Node h) {
// assert (h != null);
// assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
flipColors(h);
if (isRed(h.left.left)) {
h = rotateRight(h);
flipColors(h);
}
return h;
}
// restore red-black tree invariant
private Node balance(Node h) {
// assert (h != null);
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.size = size(h.left) + size(h.right) + 1;
return h;
}
/***************************************************************************
* Utility functions.
***************************************************************************/
/**
* Returns the height of the BST (for debugging).
* @return the height of the BST (a 1-node tree has height 0)
*/
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));
}
/***************************************************************************
* Ordered symbol table methods.
***************************************************************************/
/**
* Returns the smallest key in the symbol table.
* @return the smallest key in the symbol table
* @throws NoSuchElementException if the symbol table is empty
*/
public Key min() {
if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
return min(root).key;
}
// 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);
}
/**
* Returns the largest key in the symbol table.
* @return the largest key in the symbol table
* @throws NoSuchElementException if the symbol table is empty
*/
public Key max() {
if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
return max(root).key;
}
// the largest key in the subtree rooted at x; null if no such key
private Node max(Node x) {
// assert x != null;
if (x.right == null) return x;
else return max(x.right);
}
/**
* Returns the largest key in the symbol table less than or equal to {@code key}.
* @param key the key
* @return the largest key in the symbol table less than or equal to {@code key}
* @throws NoSuchElementException if there is no such key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Key floor(Key key) {
if (key == null) throw new IllegalArgumentException("argument to floor() is null");
if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table");
Node x = floor(root, key);
if (x == null) return null;
else return x.key;
}
// the largest key in the subtree rooted at x less than or equal to the given key
private Node floor(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if (t != null) return t;
else return x;
}
/**
* Returns the smallest key in the symbol table greater than or equal to {@code key}.
* @param key the key
* @return the smallest key in the symbol table greater than or equal to {@code key}
* @throws NoSuchElementException if there is no such key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Key ceiling(Key key) {
if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table");
Node x = ceiling(root, key);
if (x == null) return null;
else return x.key;
}
// the smallest key in the subtree rooted at x greater than or equal to the given key
private Node ceiling(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp > 0) return ceiling(x.right, key);
Node t = ceiling(x.left, key);
if (t != null) return t;
else return x;
}
/**
* Return the kth smallest key in the symbol table.
* @param k the order statistic
* @return the {@code k}th smallest key in the symbol table
* @throws IllegalArgumentException unless {@code k} is between 0 and
* <em>n</em>–1
*/
public Key select(int k) {
if (k < 0 || k >= size()) {
throw new IllegalArgumentException("argument to select() is invalid: " + k);
}
Node x = select(root, k);
return x.key;
}
// the key of rank k in the subtree rooted at x
private Node select(Node x, int k) {
// assert x != null;
// assert k >= 0 && k < size(x);
int t = size(x.left);
if (t > k) return select(x.left, k);
else if (t < k) return select(x.right, k-t-1);
else return x;
}
/**
* Return the number of keys in the symbol table strictly less than {@code key}.
* @param key the key
* @return the number of keys in the symbol table strictly less than {@code key}
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public int rank(Key key) {
if (key == null) throw new IllegalArgumentException("argument to rank() is null");
return rank(key, root);
}
// number of keys less than key in the subtree rooted at x
private int rank(Key key, Node x) {
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);
}
/***************************************************************************
* Check integrity of red-black tree data structure.
***************************************************************************/
private boolean check() {
if (!isBST()) System.out.println("Not in symmetric order");
if (!isSizeConsistent()) System.out.println("Subtree counts not consistent");
if (!is23()) System.out.println("Not a 2-3 tree");
if (!isBalanced()) System.out.println("Not balanced");
return isBST() && isSizeConsistent() && is23() && isBalanced();
}
// does this binary tree satisfy symmetric order?
// Note: this test also ensures that data structure is a binary tree since order is strict
private boolean isBST() {
return isBST(root, null, null);
}
// is the tree rooted at x a BST with all keys strictly between min and max
// (if min or max is null, treat as empty constraint)
// Credit: Bob Dondero's elegant solution
private boolean isBST(Node x, Key min, Key max) {
if (x == null) return true;
if (min != null && x.key.compareTo(min) <= 0) return false;
if (max != null && x.key.compareTo(max) >= 0) return false;
return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
}
// are the size fields correct?
private boolean isSizeConsistent() { return isSizeConsistent(root); }
private boolean isSizeConsistent(Node x) {
if (x == null) return true;
if (x.size != size(x.left) + size(x.right) + 1) return false;
return isSizeConsistent(x.left) && isSizeConsistent(x.right);
}
// Does the tree have no red right links, and at most one (left)
// red links in a row on any path?
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);
}
// do all paths from root to leaf have same number of black edges?
private boolean isBalanced() {
int black = 0; // number of black links on path from root to min
Node x = root;
while (x != null) {
if (!isRed(x)) black++;
x = x.left;
}
return isBalanced(root, black);
}
// does every path from the root to a leaf have the given number of black links?
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);
}
/**
* Unit tests the {@code RedBlackBST} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
RedBlackTree<String, Integer> st = new RedBlackTree<String, Integer>();
Scanner sc = new Scanner(System.in);
int i=0;
String key = sc.next();
st.put(key, i++);
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.