Answer Happy

============================================ Requirements
// 1. Implement a RedBlackTree class by extending the
BinarySearchTree class.
// Hint: The implementation of binary search tree and binary tree
with linked structure are provided
// (BinarySearchTree.java, LinkedBinaryTree.java,
BTnode.java).
//
// 2. A "color" variable is added to the BTNode class
//
// Your output should be as follows:
// ============================= Test RedBlackTree
// ------------------ Inserting 1
// inOrder: 1-Black
// ------------------ Inserting 3
// inOrder: 1-Black 3-Red
// ------------------ Inserting 4
// inOrder: 1-Red 3-Black 4-Red
// ------------------ Inserting 5
// inOrder: 1-Black 3-Black 4-Black 5-Red

// ------------------ Inserting 2
// inOrder: 1-Black 2-Red 3-Black 4-Black
5-Red
// ------------------ Inserting 6
// inOrder: 1-Black 2-Red 3-Black 4-Red
5-Black 6-Red
// 1-Black with parent 3 and leftChild: null and rightChild:
2
// 3-Black with parent null and leftChild: 1 and rightChild:
5
// 4-Red with parent 5 and leftChild: null and rightChild:
null
// 5-Black with parent 3 and leftChild: 4 and rightChild: 6
// 2-Red with parent 1 and leftChild: null and rightChild:
null
// 6-Red with parent 5 and leftChild: null and rightChild: null
// ------------------ Deleting 3-Black
// inOrder: 1-Black 2-Black 4-Red 5-Black
6-Red
// 1-Black with parent 2 and leftChild: null and rightChild:
null
// 4-Red with parent 5 and leftChild: null and rightChild:
null
// 5-Black with parent 2 and leftChild: 4 and rightChild: 6
// 2-Black with parent null and leftChild: 1 and rightChild:
5
// 6-Red with parent 5 and leftChild: null and rightChild: null
// ------------------ Deleting 4-Red
// inOrder: 1-Black 2-Black 5-Black 6-Red

// 1-Black with parent 2 and leftChild: null and rightChild:
null
// 5-Black with parent 2 and leftChild: null and rightChild:
6
// 2-Black with parent null and leftChild: 1 and rightChild:
5
// 6-Red with parent 5 and leftChild: null and rightChild: null
// ------------------ Deleting 1-Black
// ----- case 4
// inOrder: 2-Black 5-Black 6-Black

// 5-Black with parent null and leftChild: 2 and rightChild:
6
// 2-Black with parent 5 and leftChild: null and rightChild:
null
// 6-Black with parent 5 and leftChild: null and rightChild:
null
// =============================================== Note
//
// 1. DO NOT DELETE ANY COMMENT!!!
// 2. Modify the file name to "RedBlackTree.java" before
compiling it.
//
// ===============================================
public class RedBlackTree<E extends Comparable<E>>
extends BinarySearchTree<E> {

public RedBlackTree(BTNode<E> root){
super(root);

super.getRoot().setColor("Black");
}
// You might create more auxiliary methods
here
public void leftRotate(BTNode<E> x) {
//
System.out.println("------------ Call leftRotate()");
BTNode<E> y =
x.getRightChild();
x.setRightChild(y.getLeftChild());
BTNode<E> p =
x.getParent();
if (isRoot(x)) {


y.setParent(p);

setRoot(y);

y.setColor("Black");
//
System.out.println(x.getElement() + " was root! " + y.getElement()
+ " is the new root!");
} else {
if
(x.isLeftChild()) {

p.setLeftChild(y);
} else {

p.setRightChild(y);
}
}
y.setLeftChild(x);
}
public void rightRotate(BTNode<E> x) {
//
System.out.println("------------ Call rightRotate()");
BTNode<E> y =
x.getLeftChild();
x.setLeftChild(y.getRightChild());
BTNode<E> p =
x.getParent();
if (isRoot(x)) {

y.setParent(p);

setRoot(y);

y.setColor("Black");
//
System.out.println(x.getElement() + " was root! " + y.getElement()
+ " is the new root!");
} else {
if
(x.isLeftChild()) {

p.setLeftChild(y);
} else {

p.setRightChild(y);
}
}
y.setRightChild(x);
}

@Override
public void inOrder(BTNode<E> node) {
// override inOrder method to
print out node color
if(node == null) {
return
;
}
if(node.getLeftChild() !=
null) {

inOrder(node.getLeftChild());
}

System.out.print(node.getElement() + "-" + node.getColor() +
" ");
if(node.getRightChild() !=
null) {

inOrder(node.getRightChild());
}
}
@Override
public void insert(BTNode<E> node){
super.insert(node);
BTNode<E> z = node;
// COMPLETE THIS BLOCK
}
public void deleteWithColorConsidered(BTNode<E>
node){
BTNode<E> target =
this.search(node.getElement());
if (target == null) {

System.out.println("Did not find the target!");

return;
}

// realDeletedNode is the
node we actually delete.
BTNode<E>
realDeletedNode = this.getRealDeletedNode(target);
//
System.out.println(target.toString());
//
System.out.println(realDeletedNode.toString());
if (realDeletedNode ==
getRoot()) {

setRoot(null);

return;
}
// delete the
realDeletedNode

if(realDeletedNode.isLeftChild()){

realDeletedNode.getParent().setLeftChild(null);
}else{

realDeletedNode.getParent().setRightChild(null);
}
// replace the target with
the realDeletedNode
if (realDeletedNode !=
target) {
if
(isRoot(target)) {

setRoot(realDeletedNode);
} else
{

if(target.isLeftChild()){


target.getParent().setLeftChild(realDeletedNode);

}else{


target.getParent().setRightChild(realDeletedNode);

}
}

realDeletedNode.setLeftChild(target.getLeftChild());

realDeletedNode.setRightChild(target.getRightChild());
realDeletedNode.setColor(target.getColor()); // This step is
necessary!
}
}
@Override
public void delete(BTNode<E> node){
// COMPLETE THIS BLOCK
// Eventually, a node with at
least one child missing is deleted.
BTNode<E> target =
super.search(node.getElement());
if (target == null) {

System.out.println("Did not find the target!");

return;
}
// realDeletedNode is the
node we actually delete.
BTNode<E>
realDeletedNode = super.getRealDeletedNode(target);
//
System.out.println("=========target:" + target.getElement() + "-" +
target.getColor());
//
System.out.println("=========realDeletedNode:" +
realDeletedNode.getElement() + "-" +
realDeletedNode.getColor());
// If this node is red — no
violation occurs.

if(realDeletedNode.getColor().equals("Red")) {
// call delete
method

deleteWithColorConsidered(node);
return;
}
// If this node is black, we
start the fix-up with the deleted node’s child x (could be a black
dummy leaf)
BTNode<E> pOfRealDeletedNode
= realDeletedNode.getParent();
BTNode<E> x = null;
if (realDeletedNode.getLeftChild()
!= null) {
x =
realDeletedNode.getLeftChild();
} else {

x =
realDeletedNode.getRightChild();

}
// w is the sibling of x in the
tree after deletion
BTNode<E> w =
realDeletedNode.getSibling();
// x may be a dummy leave, but w
cannot be null,
// as realDeletedNode is
black!!
if (w == null) {

System.out.println("Error!! w cannot be null!");
return;
}
// call delete method

deleteWithColorConsidered(node);
// If x is red, color it
black.
if (x != null &&
x.getColor().equals("Red")) {

x.setColor("Black");
return;
}
// If x is the root of the tree
— just color it black.
if (isRoot(x)) {

x.setColor("Black");
return;
}
// O/w (i.e., x is black &
not a root), we’re looking into x’s sibling
// x might be null, i.e. a dummy
leaf!
while (true) {
if (isRoot(x))
{

x.setColor("Black");

return;
}
BTNode<E> xp = w.getParent(); // xp must exist, as w is
not null.