FIGURE 9.75 Red Black Rem 6. Complete the RedBlackTree class by coding the missi
ID: 3832124 • Letter: F
Question
FIGURE 9.75 Red Black Rem 6. Complete the RedBlackTree class by coding the missing methods for removal. The methods remove and findLargestChild are adapted from the corresponding methods of the BinarySearchTree class. These adaptations are similar to those done for the AVL tree. A data field fixupRequired performs a role analogous to the decrease data field in the AVL tree. It is set when a black node is removed. Upon return from a method that can remove a node, this variable is tested. If the removal is from the right, then a new method fixupRight is called. If the removal is from the left, then a new method fixupleft is called The fixupRight method must consider five cases, as follows: Case 1: Parent is red and sibling has a red right child. Figure 9.75(a) shows a red node P that is the root of a subtree that has lost a black node X from its right subtree. The root of the left sub tree is S, and it must be a black node. If this subtree has a red right child, as shown in the figure, we can restore the black balance. First we rotate the left subtree left and change the color of the parent to black (see Figure men we rotate right about the parentas shown in Figure 9.75 (c) This restores the black balance. As shown in the figure, the node S may also have a left child. This does not affect the results. S (b) (a) (c) Case 2: Parent is red, and sibling has only a left red child. Figure 9,76(a) shows the case where the red parent P has a left child S that has a red left child L In this case, we change the color of S to red and the color of P to black. Then we rotate right as shown in Figure 9.76(b) Case 3: Parent is red, and the left child has no red children. Figure 9.77(a) shows the case where the red parent P has a left child S that has no children. As in the next two cases, this fixup process is started at the bottom of the tree but can move up the tree. In this case, S may have black chil dren, and X may represent the root of a subtree whose black height is one less than the black height of S.The correction is quite easy. We change P to black and S to red (see Figure 9.77(b)). Now the balance is restored, and the black height at Premains the same as it was before the black height at X was reducedExplanation / Answer
RedBlackTree.java
public class RedBlackTree<E extends Comparable<E>>
extends BinarySearchTreeWithRotate<E> {
private static class RedBlackNode<E> extends Node<E> {
private boolean isRed;
public RedBlackNode(E item) {
super(item);
isRed = true;
}
@Override
public String toString() {
if (isRed) {
return "Red : " + super.toString();
} else {
return "Black: " + super.toString();
}
}
}
private boolean fixupRequired;
@Override
public boolean add(E item) {
if (root == null) {
root = new RedBlackNode<E>(item);
((RedBlackNode<E>) root).isRed = false; // root is black.
return true;
} else {
root = add((RedBlackNode<E>) root, item);
((RedBlackNode<E>) root).isRed = false; // root is always black.
return addReturn;
}
}
private Node<E> add(RedBlackNode<E> localRoot, E item) {
if (item.compareTo(localRoot.data) == 0) {
// item already in the tree.
addReturn = false;
return localRoot;
} else if (item.compareTo(localRoot.data) < 0) {
// item < localRoot.data.
if (localRoot.left == null) {
// Create new left child.
localRoot.left = new RedBlackNode<E>(item);
addReturn = true;
return localRoot;
} else { // Need to search.
// Check for two red children, swap colors if found.
moveBlackDown(localRoot);
// Recursively add on the left.
localRoot.left = add((RedBlackNode<E>) localRoot.left, item);
// See whether the left child is now red
if (((RedBlackNode<E>) localRoot.left).isRed) {
if (localRoot.left.left != null && ((RedBlackNode<E>) localRoot.left.left).isRed) {
// Left-left grandchild is also red.
// Single rotation is necessary.
((RedBlackNode<E>) localRoot.left).isRed = false;
localRoot.isRed = true;
return rotateRight(localRoot);
} else if (localRoot.left.right != null && ((RedBlackNode<E>) localRoot.left.right).isRed) {
// Left-right grandchild is also red.
// Double rotation is necessary.
localRoot.left = rotateLeft(localRoot.left);
((RedBlackNode<E>) localRoot.left).isRed = false;
localRoot.isRed = true;
return rotateRight(localRoot);
}
}
return localRoot;
}
} else { // item > localRoot.data
/*<exercise chapter="9" section="3" type="programming" number="1">*/
if (localRoot.right == null) {
// create new right child
localRoot.right = new RedBlackNode<E>(item);
addReturn = true;
return localRoot;
} else { // need to search
// check for two red children swap colors
moveBlackDown(localRoot);
// recursively insert on the right
localRoot.right =
add((RedBlackNode<E>) localRoot.right, item);
// see if the right child is now red
if (((RedBlackNode) localRoot.right).isRed) {
if (localRoot.right.right != null && ((RedBlackNode) localRoot.right.right).isRed) {
// right-right grandchild is also red
// single rotate is necessary
((RedBlackNode) localRoot.right).isRed = false;
localRoot.isRed = true;
return rotateLeft(localRoot);
} else if (localRoot.right.left != null && ((RedBlackNode<E>) localRoot.right.left).isRed) {
// left-right grandchild is also red
// double rotate is necessary
localRoot.right = rotateRight(localRoot.right);
((RedBlackNode<E>) localRoot.right).isRed = false;
localRoot.isRed = true;
return rotateLeft(localRoot);
}
}
return localRoot;
}
/*</exercise>*/
}
}
private void moveBlackDown(RedBlackNode<E> localRoot) {
// see if both children are red
if (localRoot.left != null && localRoot.right != null && ((RedBlackNode<E>) localRoot.left).isRed && ((RedBlackNode<E>) localRoot.right).isRed) {
//make them black and myself red
((RedBlackNode<E>) localRoot.left).isRed = false;
((RedBlackNode<E>) localRoot.right).isRed = false;
localRoot.isRed = true;
}
}
@Override
public E delete(E item) {
fixupRequired = false;
if (root == null) {
return null;
} else {
int compareReturn = item.compareTo(root.data);
if (compareReturn == 0) {
E oldValue = root.data;
root = findReplacement(root);
if (fixupRequired) {
root = fixupLeft(root);
}
return oldValue;
} else if (compareReturn < 0) {
if (root.left == null) {
return null;
} else {
E oldValue = removeFromLeft(root, item);
if (fixupRequired) {
root = fixupLeft(root);
}
return oldValue;
}
} else {
if (root.right == null) {
return null;
} else {
E oldValue = removeFromRight(root, item);
if (fixupRequired) {
root = fixupRight(root);
}
return oldValue;
}
}
}
}
private E removeFromLeft(Node<E> parent, E item) {
if (item.compareTo(parent.left.data) < 0) {
if (parent.left.left == null) {
return null;
} else {
E oldValue = removeFromLeft(parent.left, item);
if (fixupRequired) {
parent.left = fixupLeft(parent.left);
}
return oldValue;
}
} else if (item.compareTo(parent.left.data) > 0) {
if (parent.left.right == null) {
return null;
} else {
E oldValue = removeFromRight(parent.left, item);
if (fixupRequired) {
parent.left = fixupRight(parent.left);
}
return oldValue;
}
} else {
E oldValue = parent.left.data;
parent.left = findReplacement(parent.left);
return oldValue;
}
}
private E removeFromRight(Node<E> parent, E item) {
if (item.compareTo(parent.right.data) < 0) {
if (parent.right.left == null) {
return null;
} else {
E oldValue = removeFromLeft(parent.right, item);
if (fixupRequired) {
parent.right = fixupLeft(parent.right);
}
return oldValue;
}
} else if (item.compareTo(parent.right.data) > 0) {
if (parent.right.right == null) {
return null;
} else {
E oldValue = removeFromRight(parent.right, item);
if (fixupRequired) {
parent.right = fixupRight(parent.right);
}
return oldValue;
}
} else {
E oldValue = parent.right.data;
parent.right = findReplacement(parent.right);
return oldValue;
}
}
private Node<E> findReplacement(Node<E> node) {
if (node.left == null) {
if (((RedBlackNode<E>) node).isRed) {
// can always remove a red node
return node.right;
} else if (node.right == null) {
// We are removing a black leaf
fixupRequired = true;
return null;
} else if (((RedBlackNode<E>) node.right).isRed) {
// replace black node with red child
((RedBlackNode<E>) node.right).isRed = false;
return node.right;
} else {
// a black node cannot have only one black child
throw new RuntimeException("Invalid Red-Black " +
"Tree Structure");
}
} else if (node.right == null) {
if (((RedBlackNode<E>) node).isRed) {
// can always remove a red node
return node.left;
} else if (((RedBlackNode<E>) node.left).isRed) {
((RedBlackNode<E>) node.left).isRed = false;
return node.left;
} else {
// a black node cannot have only one black child
throw new RuntimeException("Invalid Red-Black " +
"Tree structure");
}
} else {
if (node.left.right == null) {
node.data = node.left.data;
if (((RedBlackNode<E>) node.left).isRed) {
node.left = node.left.left;
} else if (node.left.left == null) {
fixupRequired = true;
node.left = null;
} else if (((RedBlackNode<E>) node.left.left).isRed) {
((RedBlackNode<E>) node.left.left).isRed = false;
node.left = node.left.left;
} else {
throw new RuntimeException("Invalid Red-Black " +
"Tree structure");
}
return node;
} else {
node.data = findLargestChild(node.left);
if (fixupRequired) {
node.left = fixupRight(node.left);
}
if (fixupRequired) {
return fixupLeft(node);
} else {
return node;
}
}
}
}
private E findLargestChild(Node<E> parent) {
if (parent.right.right == null) {
E returnValue = parent.right.data;
if (((RedBlackNode<E>) parent.right).isRed) {
parent.right = parent.right.left;
} else if (parent.right.left == null) {
fixupRequired = true;
parent.right = null;
} else if (((RedBlackNode<E>) parent.right.left).isRed) {
((RedBlackNode<E>) parent.right.left).isRed = false;
parent.right = parent.right.left;
} else {
throw new RuntimeException("Invalid Red-Black " +
"Tree structure");
}
return returnValue;
} else {
E returnValue = findLargestChild(parent.right);
if (fixupRequired) {
parent.right = fixupRight(parent.right);
}
return returnValue;
}
}
private Node<E> fixupRight(Node<E> localRoot) {
// See if the right sub-tree has a red local root
if (localRoot.right != null &&
((RedBlackNode<E>) localRoot.right).isRed) {
//Then paint it black and we are done
((RedBlackNode<E>) localRoot.right).isRed = false;
fixupRequired = false;
return localRoot;
}
RedBlackNode<E> s = (RedBlackNode<E>) localRoot.left;
if (s.isRed) { //Case 1
s.isRed = false;
((RedBlackNode<E>) localRoot).isRed = true;
Node<E> returnValue = rotateRight(localRoot);
returnValue.right = fixupRight(returnValue.right);
if (fixupRequired) {
return fixupRight(returnValue);
} else {
return returnValue;
}
} else { // Case 2, 3, or 4
if ((s.left == null && s.right == null) ||
((s.left != null &&
!((RedBlackNode<E>) s.left).isRed) &&
(s.right != null &&
!((RedBlackNode<E>) s.right).isRed))) {
// Case 2
s.isRed = true;
return localRoot;
} else {
if (s.right != null && ((RedBlackNode<E>) s.right).isRed) {
// Case 3
s.isRed = true;
((RedBlackNode<E>) s.right).isRed = false;
localRoot.left = rotateLeft(s);
s = (RedBlackNode<E>) localRoot.left;
}
// Case 4
s.isRed = ((RedBlackNode<E>) localRoot).isRed;
((RedBlackNode<E>) s.left).isRed = false;
((RedBlackNode<E>) localRoot).isRed = false;
fixupRequired = false;
return rotateRight(localRoot);
}
}
}
private Node<E> fixupLeft(Node<E> localRoot) {
// See if the left sub-tree has a red local root
if (localRoot.left != null &&
((RedBlackNode<E>) localRoot.left).isRed) {
//Then paint it black and we are done
((RedBlackNode<E>) localRoot.left).isRed = false;
fixupRequired = false;
return localRoot;
}
RedBlackNode<E> s = (RedBlackNode<E>) localRoot.right;
if (s.isRed) { //Case 1
s.isRed = false;
((RedBlackNode<E>) localRoot).isRed = true;
Node<E> returnValue = rotateLeft(localRoot);
returnValue.left = fixupLeft(returnValue.left);
if (fixupRequired) {
return fixupLeft(returnValue);
} else {
return returnValue;
}
} else { // Case 2, 3, or 4
if ((s.right == null && s.left == null) ||
((s.right != null &&
!((RedBlackNode<E>) s.right).isRed) && (s.left != null &&
!((RedBlackNode<E>) s.left).isRed))) {
// Case 2
s.isRed = true;
return localRoot;
} else {
if (s.left != null && ((RedBlackNode<E>) s.left).isRed) {
// Case 3
s.isRed = true;
((RedBlackNode<E>) s.left).isRed = false;
localRoot.right = rotateRight(s);
s = (RedBlackNode<E>) localRoot.right;
}
// Case 4
s.isRed = ((RedBlackNode<E>) localRoot).isRed;
((RedBlackNode<E>) s.right).isRed = false;
((RedBlackNode<E>) localRoot).isRed = false;
fixupRequired = false;
return rotateLeft(localRoot);
}
}
}
/*</exercise>*/
}
/*</listing>*/
BinarySearchTreeWithRotate.java
public class BinarySearchTreeWithRotate<E extends Comparable<E>>
extends BinarySearchTree<E> {
protected Node<E> rotateRight(Node<E> root) {
Node<E> temp = root.left;
root.left = temp.right;
temp.right = root;
return temp;
}
protected Node<E> rotateLeft(Node<E> localRoot) {
Node<E> temp = localRoot.right;
localRoot.right = temp.left;
temp.left = localRoot;
return temp;
}
/*</exercise>*/
}
BinarySearchTree.java
public class BinarySearchTree<E extends Comparable<E>>
extends BinaryTree<E>
implements SearchTree<E> {
// Data Fields
/** Return value from the public add method. */
protected boolean addReturn;
/** Return value from the public delete method. */
protected E deleteReturn;
public E find(E target) {
return find(root, target);
}
private E find(Node<E> localRoot, E target) {
if (localRoot == null) {
return null;
}
// Compare the target with the data field at the root.
int compResult = target.compareTo(localRoot.data);
if (compResult == 0) {
return localRoot.data;
} else if (compResult < 0) {
return find(localRoot.left, target);
} else {
return find(localRoot.right, target);
}
}
public boolean add(E item) {
root = add(root, item);
return addReturn;
}
private Node<E> add(Node<E> localRoot, E item) {
if (localRoot == null) {
// item is not in the tree insert it.
addReturn = true;
return new Node<E>(item);
} else if (item.compareTo(localRoot.data) == 0) {
// item is equal to localRoot.data
addReturn = false;
return localRoot;
} else if (item.compareTo(localRoot.data) < 0) {
// item is less than localRoot.data
localRoot.left = add(localRoot.left, item);
return localRoot;
} else {
// item is greater than localRoot.data
localRoot.right = add(localRoot.right, item);
return localRoot;
}
}
public E delete(E target) {
root = delete(root, target);
return deleteReturn;
}
private Node<E> delete(Node<E> localRoot, E item) {
if (localRoot == null) {
// item is not in the tree.
deleteReturn = null;
return localRoot;
}
// Search for item to delete.
int compResult = item.compareTo(localRoot.data);
if (compResult < 0) {
// item is smaller than localRoot.data.
localRoot.left = delete(localRoot.left, item);
return localRoot;
} else if (compResult > 0) {
// item is larger than localRoot.data.
localRoot.right = delete(localRoot.right, item);
return localRoot;
} else {
// item is at local root.
deleteReturn = localRoot.data;
if (localRoot.left == null) {
// If there is no left child, return right child
// which can also be null.
return localRoot.right;
} else if (localRoot.right == null) {
// If there is no right child, return left child.
return localRoot.left;
} else {
// Node being deleted has 2 children, replace the data
// with inorder predecessor.
if (localRoot.left.right == null) {
// The left child has no right child.
// Replace the data with the data in the
// left child.
localRoot.data = localRoot.left.data;
// Replace the left child with its left child.
localRoot.left = localRoot.left.left;
return localRoot;
} else {
// Search for the inorder predecessor (ip) and
// replace deleted nodes data with ip.
localRoot.data = findLargestChild(localRoot.left);
return localRoot;
}
}
}
}
/*</listing>*/
public boolean remove(E target) {
return delete(target) != null;
}
public boolean contains(E target) {
return find(target) != null;
}
private E findLargestChild(Node<E> parent) {
// If the right child has no right child, it is
// the inorder predecessor.
if (parent.right.right == null) {
E returnValue = parent.right.data;
parent.right = parent.right.left;
return returnValue;
} else {
return findLargestChild(parent.right);
}
}
/*</listing>*/
}
/*</listing>*/
BinaryTree.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.Serializable;
public class BinaryTree<E> implements Serializable {
protected static class Node<E> implements Serializable {
// Data Fields
/** The information stored in this node. */
public E data;
/** Reference to the left child. */
public Node<E> left;
/** Reference to the right child. */
public Node<E> right;
public Node(E data) {
this.data = data;
left = null;
right = null;
}
@Override
public String toString() {
return data.toString();
}
}
protected Node<E> root;
/** Construct an empty BinaryTree */
public BinaryTree() {
root = null;
}
protected BinaryTree(Node<E> root) {
this.root = root;
}
public BinaryTree(E data, BinaryTree<E> leftTree,
BinaryTree<E> rightTree) {
root = new Node<E>(data);
if (leftTree != null) {
root.left = leftTree.root;
} else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
} else {
root.right = null;
}
}
public BinaryTree<E> getLeftSubtree() {
if (root != null && root.left != null) {
return new BinaryTree<E>(root.left);
} else {
return null;
}
}
public BinaryTree<E> getRightSubtree() {
if (root != null && root.right != null) {
return new BinaryTree<E>(root.right);
} else {
return null;
}
}
public E getData() {
if (root != null) {
return root.data;
} else {
return null;
}
}
public boolean isLeaf() {
return (root == null || (root.left == null && root.right == null));
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, 1, sb);
return sb.toString();
}
private void preOrderTraverse(Node<E> node, int depth,
StringBuilder sb) {
for (int i = 1; i < depth; i++) {
sb.append(" ");
}
if (node == null) {
sb.append("null ");
} else {
sb.append(node.toString());
sb.append(" ");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}
public static BinaryTree<String> readBinaryTree(BufferedReader bR) throws IOException {
// Read a line and trim leading and trailing spaces.
String data = bR.readLine().trim();
if (data.equals("null")) {
return null;
} else {
BinaryTree<String> leftTree = readBinaryTree(bR);
BinaryTree<String> rightTree = readBinaryTree(bR);
return new BinaryTree<String>(data, leftTree, rightTree);
}
}
/*</listing>*/
}
/*</listing>*/
SearchTree.java
public interface SearchTree<E extends Comparable<E>> {
boolean add(E item);
boolean contains(E target);
E find(E target);
E delete(E target);
boolean remove(E target);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.