For this assignment, you will be implementing a version of a Red-Black Tree. You
ID: 3859526 • Letter: F
Question
For this assignment, you will be implementing a version of a Red-Black Tree. Your Red-Black tree will be implemented as a Map where each node will store a key (which must be unique) and a value. You must implement your Tree to be generic (keys can be any type that is a subclass of Comparable, and the value can be any type). You are not allowed to use any sorting algorithms in your implementation.
The Node Class
Your node class should include member variables for the key and value you want to store in the node as well as member variables which are pointers to the left and right subtrees, and the parent of the node.
You will also want to keep track of the color of the node.
Add any additional methods / constructors you feel will help. If you are unsure of your design you MUST talk to me ahead of time for approval.
The RBTree Class
The RBTree class should have a member variable that points to the root node of the entire tree.
The RBTree class should have a constant member variable Node with a value of null for its key, null for its value, and all of its pointers are also null. This will be your special NIL leaf that is required of the RBTree. This special node should only have one instantiation in memory (I will be looking for this.)
Add whatever constructors you feel are necessary.
You will want to include the following functionality:a way to find the grandparent of any given node
remember to check for cases where a node might not have a grandparent.
a way to find the uncle of any given node
remember to check for cases where a node might not have an uncle.
a left rotate function
remember to update the parent pointer of each node that changes
remember to connect the correct node back into the tree after the rotation
a right rotate function
remember to update the parent pointer of each node that changes
remember to connect the correct node back into the tree after the rotation
a function to start the insertion process of a new node. (most likely a helper method that calls other methods.)
a function the performs a normal binary search tree insertion (this will be used by your insert method)
a function which checks to see if the tree violates any of the rules of a RB tree and makes the necessary corrections
use the algorithm from the lecture slides.
this will be used by your insert method
add functions for all of the traversals. these functions should return an ArrayList of Nodes in the correct order. you should also incorporate these into your gui (have buttons that can show the results of each traversal).
NOTE: You must implement these WITHOUT using recursion.
preorder: HINT: You will need to use a Stack to implement preorder nonrecursively. Research how to use the Stack class in Java.
inorder: HINT: You will need to use a Stack to implement inorder nonrecursively. Research how to use the Stack class in Java.
postorder: HINT: You will need to use a Stack and a Set to implement postorder nonrecursively. The Set will store nodes that have already been visited. Also you will need to keep track of if you are returning from the left or right subtree.
breadth-first: HINT: You will need to use a Queue to implement breadth-first. Research how to use a Queue in Java.
add any other functionality you feel is necessary. If you are unsure of something be sure to have your design approved by me ahead of time.
Think very carefully about what should be public, private, and protected in your implementation. I will be deducting points when things have the wrong access modifiers.
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; // 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 RedBlackBST() {
}
/***************************************************************************
* 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");
if (val == null) {
delete(key);
retur
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.