For this assignment, you will be implementing a version of a Red-Black Tree . Yo
ID: 3862269 • 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
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
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.
Explanation / Answer
Red-Black Trees:
A red–black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties.
Red–black trees, like all binary search trees, allow efficient in-order traversal (that is: in the order Left–Root–Right) of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree of n nodes, having the least possible tree height, results in O(log n) search time.
Properties:
Some definitions: the number of black nodes from the root to a node is the node's black depth; the uniform number of black nodes in all paths from root to the leaves is called the black height of the red–black tree.
Program code:RBTree.java
Implemented as a subclass of BST, with an inner class that is a subclass of BST.Node
public class RBTree<K extends Comparable<K>, V> extends BST<K,V>
{
public class Node extends BST<K,V>.Node {
protected boolean isBlack;
/**
* Constructor for a Node. Makes the node red.
**/
public Node(K key, V value) {
super(key, value);
isBlack = false;
}
/**
* return true if this node is black
*/
protected boolean isBlack() {
return isBlack;
}
/**
* return true if this node is red
*/
protected boolean isRed() {
return !isBlack;
}
protected void blacken() {
isBlack = true;
}
/**
* Make this node red.
*/
protected void redden() {
isBlack = false;
}
/*do a left rotation on this node
protected void leftRotate() {
Node x = this;
BST<K,V>.Node y = x.right;
x.right = y.left;
if (y.left != sentinel)
y.left.parent = x;
y.parent = x.parent;
if (x.parent == sentinel)
root = y;
else if (x == x.parent.left)
x.parent.left = y;
else
x.parent.right = y;
y.left = x;
x.parent = y;
}
/**
* Do a right rotation around this node.
*/
protected void rightRotate() {
Node y = this;
BST<K,V>.Node x = y.left;
y.left = x.right;
if (x.right != sentinel)
x.right.parent = y;
x.parent = y.parent;
if (y.parent == sentinel)
root = x;
else if (y == y.parent.right)
y.parent.right = x;
else
x.parent.left = x;
x.right = y;
y.parent = x;
}
protected void rbInsertFixup() {
Node z = this;
while (((RBTree<K,V>.Node) z.parent).isRed()) {
if (z.parent == z.parent.parent.left) {
// z's parent is a left child.
Node y = (RBTree<K,V>.Node) z.parent.parent.right;
if (y.isRed()) {
// Case 1: z's uncle y is red.
System.out.println("rbInsertFixup: Case 1 left");
((RBTree<K,V>.Node) z.parent).blacken();
y.blacken();
((RBTree<K,V>.Node) z.parent.parent).redden();
z = (RBTree<K,V>.Node) z.parent.parent;
}
else {
if (z == z.parent.right) {
// Case 2: z's uncle y is black and z is a right child.
// System.out.println("rbInsertFixup: Case 2 left");
z = (RBTree<K,V>.Node) z.parent;
z.leftRotate();
}
// Case 3: z's uncle y is black and z is a left child.
// System.out.println("rbInsertFixup: Case 3 left");
((RBTree<K,V>.Node) z.parent).blacken();
((RBTree<K,V>.Node) z.parent.parent).redden();
((RBTree<K,V>.Node) z.parent.parent).rightRotate();
}
}
else {
// z's parent is a right child. Do the same as when z's parent is a left child, but exchange "left" and "right."//
Node y = (RBTree<K,V>.Node) z.parent.parent.left;
if (y.isRed()) {
// Case 1: z's uncle y is red.
// System.out.println("rbInsertFixup: Case 1 right");
((RBTree<K,V>.Node) z.parent).blacken();
y.blacken();
((RBTree<K,V>.Node) z.parent.parent).redden();
z = (RBTree<K,V>.Node) z.parent.parent;
}
else {
if (z == z.parent.left) {
// Case 2: z's uncle y is black and z is a left child.
// System.out.println("rbInsertFixup: Case 2 right");
z = (RBTree<K,V>.Node) z.parent;
z.rightRotate();
}
// Case 3: z's uncle y is black and z is a right child.
// System.out.println("rbInsertFixup: Case 3 right");
((RBTree<K,V>.Node) z.parent).blacken();
((RBTree<K,V>.Node) z.parent.parent).redden();
((RBTree<K,V>.Node) z.parent.parent).leftRotate();
}
}
} // The root is always black.
((RBTree<K,V>.Node) root).blacken();
}
//Same as transplant from the BST class, except that we make v have the same parent as this node, even if v is the sentinel.
protected void transplant(Node v)
{
super.transplant(v);
v.parent = this.parent; // even if v is the sentinel
}
/**
* Remove this node from a red-black tree.
*/
public void remove() {
Node z = this;
Node y = z; // y is the node either removed or moved within the tree
boolean yOrigWasBlack = y.isBlack(); // need to know whether y was black
Node x; // x is the node that will move into y's original position
if (z.left == sentinel) { // no left child?
x = (RBTree<K,V>.Node) z.right;
z.transplant(x); // replace z by its right child
}
else if (z.right == sentinel)
{
x = (RBTree<K,V>.Node) z.left;
z.transplant(x); // replace z by its left child
}
else
{
// Node z has two children. Its successor y is in its right subtree and has no left child.
y = (RBTree<K,V>.Node) z.right.minimum();
yOrigWasBlack = y.isBlack();
x = (RBTree<K,V>.Node) y.right;
// replace z with y
if (y.parent == z)
x.parent = y;
else {
// If y is not z's right child, replace y as a child of its parent by
// y's right child and turn z's right child into y's right child.
y.transplant(x);
y.right = z.right;
y.right.parent = y;
}
// Replace z as a child of its parent by y and replace y's left child by z's left child.
z.transplant(y);
y.left = z.left;
y.left.parent = y;
// Give y the same color as z.
if (z.isBlack())
y.blacken();
else
y.redden();
}
Fix the possible violation of the red-black properties caused by removing a black node. This node has moved into the position of the node that was removed or moved. If the removed node was black, three problems could arise. If it was the root and a red child became the root, now the root is red. If both this node and its parent are red, we have two red nodes in a row. And moving a node y within the tree causes any simple path that had contained y to have one fewer black node.
Consider this node, x, now occupying y's original position, as having an extra black. Restore the red-black properties by pushing the extra black up in the tree until one of the following happens:
- x is a red-and-black node, and we color x singly black;
- x is the root, and we just remove the extra black; or
- having rotated and recolored, we exit the loop.
protected void rbRemoveFixup()
{
Node x = this;
Node w = null;
while (x != root && x.isBlack())
{
if (x == x.parent.left) {
w = (RBTree<K,V>.Node) x.parent.right;
if (w.isRed()) {
// Case 1: x's sibling w is red.
// System.out.println("rbRemoveFixup: Case 1 left");
w.blacken();
((RBTree<K,V>.Node) x.parent).redden();
((RBTree<K,V>.Node) x.parent).leftRotate();
w = (RBTree<K,V>.Node) x.parent.right;
}
if (((RBTree<K,V>.Node) w.left).isBlack() &&
((RBTree<K,V>.Node) w.right).isBlack()) {
// Case 2: x's sibling w is black, and both of w's children are black.
// System.out.println("rbRemoveFixup: Case 2 left");
w.redden();
x = (RBTree<K,V>.Node) x.parent;
}
else {
if (((RBTree<K,V>.Node) w.right).isBlack()) {
// Case 3: x's sibling w is black, w's left child is red,
// and w's right child is black.
// System.out.println("rbRemoveFixup: Case 3 left");
((RBTree<K,V>.Node) w.left).blacken();
w.redden();
w.rightRotate();
w = (RBTree<K,V>.Node) x.parent.right;
}
// Case 4: x's sibling w is black, and w's right child is red.
// System.out.println("rbRemoveFixup: Case 4 left");
if (((RBTree<K,V>.Node) x.parent).isBlack())
w.blacken();
else
w.redden();
((RBTree<K,V>.Node) x.parent).blacken();
((RBTree<K,V>.Node) w.right).blacken();
((RBTree<K,V>.Node) x.parent).leftRotate();
x = (RBTree<K,V>.Node) root;
}
}
else {
w = (RBTree<K,V>.Node) x.parent.left;
if (w.isRed()) {
// Case 1: x's sibling w is red.
// System.out.println("rbRemoveFixup: Case 1 right");
w.blacken();
((RBTree<K,V>.Node) x.parent).redden();
((RBTree<K,V>.Node) x.parent).rightRotate();
w = (RBTree<K,V>.Node) x.parent.left;
}
if (((RBTree<K,V>.Node) w.right).isBlack() &&
((RBTree<K,V>.Node) w.left).isBlack()) {
// Case 2: x's sibling w is black, and both of w's children are black.
// System.out.println("rbRemoveFixup: Case 2 right");
w.redden();
x = (RBTree<K,V>.Node) x.parent;
}
else {
if (((RBTree<K,V>.Node) w.left).isBlack()) {
// Case 3: x's sibling w is black, w's right child is red,
// and w's left child is black.
// System.out.println("rbRemoveFixup: Case 3 right");
((RBTree<K,V>.Node) w.right).blacken();
w.redden();
w.leftRotate();
w = (RBTree<K,V>.Node) x.parent.left;
}
// Case 4: x's sibling w is black, and w's left child is red.
// System.out.println("rbRemoveFixup: Case 4 right");
if (((RBTree<K,V>.Node) x.parent).isBlack())
w.blacken();
else
w.redden();
((RBTree<K,V>.Node) x.parent).blacken();
((RBTree<K,V>.Node) w.left).blacken();
((RBTree<K,V>.Node) x.parent).rightRotate();
x = (RBTree<K,V>.Node) root;
}
}
}
x.blacken();
}
/**
* Constructor for the RBTree class.
* Makes a sentinel that is its own parent and children, colored black.
**/
public RBTree() {
sentinel = getNewNode(null, null);
sentinel.parent = sentinel;
sentinel.left = sentinel;
sentinel.right = sentinel;
((RBTree<K,V>.Node) sentinel).blacken();
root = sentinel;
}
// Check the black-height of this RBTree and that it does not
// contain two consecutive red nodes.
public void check() {
if (root != sentinel) {
checkBlackHeight((RBTree<K,V>.Node) root);
checkReds((RBTree<K,V>.Node) root);
}
}
// Print an error message when a check fails.
private void complain(String s, Node x) {
System.err.println("Check error: " + s + " at " + x.toString());
}
// Check that x and its parent are not both red.
private void checkReds(Node x) {
if (x != sentinel) {
if (x.parent != sentinel && x.isRed() &&
((RBTree<K,V>.Node) x.parent).isRed())
complain("two consecutive red nodes", x);
checkReds((RBTree<K,V>.Node) x.left);
checkReds((RBTree<K,V>.Node) x.right);
}
}
// Return the black-height of node x.
private int checkBlackHeight(Node x) {
if (x == sentinel)
return 0;
else {
int leftBlackHeight = checkBlackHeight((RBTree<K,V>.Node) x.left) +
(((RBTree<K,V>.Node) x.left).isBlack() ? 1 : 0);
int rightBlackHeight = checkBlackHeight((RBTree<K,V>.Node) x.right) +
(((RBTree<K,V>.Node) x.right).isBlack() ? 1 : 0);
if (leftBlackHeight != rightBlackHeight)
complain("blackheight error", x);
return leftBlackHeight;
}
}
/**
* Create a new node and insert it into the RBTree
*/
public Node insert(K key, V value) {
Node z = (RBTree<K,V>.Node) super.insert(key, value);
z.left = sentinel;
z.right = sentinel;
z.redden();
z.rbInsertFixup();
return z;
}
// Overrides the getNewNode method from the superclass.
protected Node getNewNode(K key, V value) {
return new Node(key, value);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.