Question

Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....

Complete the redblacktree in Java.

Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default.

In the end of the insert method, set the root node of your red black tree to be black.

Implement the rotate() and recolor() functions, and create tests for them in a separate class.

import java.util.LinkedList;

public class BinarySearchTree<T extends Comparable<T>> {


protected static class Node<T> {
public T data;
public Node<T> parent; // null for root node
public Node<T> leftChild;
public Node<T> rightChild;

public Node(T data) {
this.data = data;
}

public boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}


@Override
public String toString() { // display subtree in order traversal
String output = "[";
LinkedList<Node<T>> q = new LinkedList<>();
q.add(this);
while (!q.isEmpty()) {
Node<T> next = q.removeFirst();
if (next.leftChild != null)
q.add(next.leftChild);
if (next.rightChild != null)
q.add(next.rightChild);
output += next.data.toString();
if (!q.isEmpty())
output += ", ";
}
return output + "]";
}
}

protected Node<T> root; // reference to root node of tree, null when empty


public void insert(T data) throws NullPointerException, IllegalArgumentException {
// null references cannot be stored within this tree
if (data == null)
throw new NullPointerException("This RedBlackTree cannot store null references.");

Node<T> newNode = new Node<>(data);
if (root == null) {
root = newNode;
} // add first node to an empty tree
else
insertHelper(newNode, root); // recursively insert into subtree
}


private void insertHelper(Node<T> newNode, Node<T> subtree) {
int compare = newNode.data.compareTo(subtree.data);
// do not allow duplicate values to be stored within this tree
if (compare == 0)
throw new IllegalArgumentException("This RedBlackTree already contains that value.");

// store newNode within left subtree of subtree
else if (compare < 0) {
if (subtree.leftChild == null) { // left subtree empty, add here
subtree.leftChild = newNode;
newNode.parent = subtree;
// otherwise continue recursive search for location to insert
} else
insertHelper(newNode, subtree.leftChild);
}

// store newNode within the right subtree of subtree
else {
if (subtree.rightChild == null) { // right subtree empty, add here
subtree.rightChild = newNode;
newNode.parent = subtree;
// otherwise continue recursive search for location to insert
} else
insertHelper(newNode, subtree.rightChild);
}
}


@Override
public String toString() {
return root.toString();
}

/**
* Performs the rotation operation on the provided nodes within this BST. When the provided child
* is a leftChild of the provided parent, this method will perform a right rotation (sometimes
* called a left-right rotation). When the provided child is a rightChild of the provided parent,
* this method will perform a left rotation (sometimes called a right-left rotation). When the
* provided nodes are not related in one of these ways, this method will throw an
* IllegalArgumentException.
*/
private void rotate(Node<T> child, Node<T> parent) throws IllegalArgumentException {
// TODO: Implement this method.
}

/**
* recolor() takes a reference to a newly added red node as its only parameter. This method may
* also be called recursively, in which case the input parameter may reference a different red
* node in the tree that potentially has a red parent node. The job of this method is to resolve
* red child under red parent red black tree property violations that are introduced by inserting
* new nodes into a red black tree. All other red black tree properties must also be preserved.
* The method should be called from insertHelper after adding a new red node to the tree (in both
* the cases of adding this new node as a left child and as a right child). No further changes to
* the insertHelper method should be made.
*/
private void recolor(Node<T> newNode) {
// TODO: Implement this method.
}


}

Homework Answers

Answer #1

/*
Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field,
all new node is red by default.

In the end of the insert method, set the root node of your red black tree to be black.

Implement the rotate() and recolor() functions, and create tests for them in a separate class

*/
import java.util.LinkedList;

public class BinarySearchTree<T extends Comparable<T>> {


protected static class Node<T> {
public T data;
public Node<T> parent; // null for root node
public Node<T> leftChild;
public Node<T> rightChild;
public String color;

public Node(T data) {
this.data = data;
this.color = "Red";
}

public boolean isBlack(){
return this.color.equals("Black");
}

public boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}


@Override
public String toString() { // display subtree in order traversal
String output = "[";
LinkedList<Node<T>> q = new LinkedList<>();
q.add(this);
while (!q.isEmpty()) {
Node<T> next = q.removeFirst();
if (next.leftChild != null)
q.add(next.leftChild);
if (next.rightChild != null)
q.add(next.rightChild);
output += next.data.toString();
if (!q.isEmpty())
output += ", ";
}
return output + "]";
}
}

protected Node<T> root; // reference to root node of tree, null when empty


public void insert(T data) throws NullPointerException, IllegalArgumentException {
// null references cannot be stored within this tree
if (data == null)
throw new NullPointerException("This RedBlackTree cannot store null references.");

Node<T> newNode = new Node<>(data);
if (root == null) {
root = newNode;
root.color = "Black";
} // add first node to an empty tree
else
insertHelper(newNode, root); // recursively insert into subtree
}


private void insertHelper(Node<T> newNode, Node<T> subtree) {
int compare = newNode.data.compareTo(subtree.data);
// do not allow duplicate values to be stored within this tree
if (compare == 0)
throw new IllegalArgumentException("This RedBlackTree already contains that value.");

// store newNode within left subtree of subtree
else if (compare < 0) {
if (subtree.leftChild == null) { // left subtree empty, add here
subtree.leftChild = newNode;
newNode.parent = subtree;
recolor(newNode);
// otherwise continue recursive search for location to insert
} else
insertHelper(newNode, subtree.leftChild);
}

// store newNode within the right subtree of subtree
else {
if (subtree.rightChild == null) { // right subtree empty, add here
subtree.rightChild = newNode;
newNode.parent = subtree;
recolor(newNode);
// otherwise continue recursive search for location to insert
} else
insertHelper(newNode, subtree.rightChild);
}
}


@Override
public String toString() {
return root.toString();
}
/**
* Performs the rotation operation on the provided nodes within this BST. When the provided child
* is a leftChild of the provided parent, this method will perform a right rotation (sometimes
* called a left-right rotation). When the provided child is a rightChild of the provided parent,
* this method will perform a left rotation (sometimes called a right-left rotation). When the
* provided nodes are not related in one of these ways, this method will throw an
* IllegalArgumentException.
*/
private void rotate(Node<T> child, Node<T> parent) throws IllegalArgumentException {

if(parent.leftChild == child){
if(parent.parent.leftChild == parent) {
parent.parent.leftChild = child;
}
else if (parent.parent.rightChild == parent){
parent.parent.rightChild = child;
}
parent.leftChild = child.rightChild;
child.rightChild = parent;
}
else if (parent.rightChild == child){
if(parent.parent.leftChild == parent) {
parent.parent.leftChild = child;
}
else if (parent.parent.rightChild == parent){
parent.parent.rightChild = child;
}
parent.rightChild = child.leftChild;
child.leftChild = parent;
}
else
throw new IllegalArgumentException("Child Parent do not match!");
}

/**
* recolor() takes a reference to a newly added red node as its only parameter. This method may
* also be called recursively, in which case the input parameter may reference a different red
* node in the tree that potentially has a red parent node. The job of this method is to resolve
* red child under red parent red black tree property violations that are introduced by inserting
* new nodes into a red black tree. All other red black tree properties must also be preserved.
* The method should be called from insertHelper after adding a new red node to the tree (in both
* the cases of adding this new node as a left child and as a right child). No further changes to
* the insertHelper method should be made.
*/
private void recolor(Node<T> newNode) {

if (newNode.parent!=null) {

// Case 1 Node is red, parent is red, grandparent is black, uncle is red
if (!newNode.isBlack()) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (!newNode.parent.parent.rightChild.isBlack()) {
newNode.parent.color = "Black";
newNode.parent.parent.rightChild.color = "Black";
newNode.parent.parent.color = "Red";
recolor(newNode.parent.parent);
}
else if (!newNode.parent.parent.leftChild.isBlack()) {
newNode.parent.color = "Black";
newNode.parent.parent.leftChild.color = "Black";
newNode.parent.parent.color = "Red";
}
}
}
}
// Case 2 Node is red, parent is red, grandparent is black, uncle is black
if(!newNode.isBlack()){
if (newNode.parent.rightChild == newNode) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.rightChild.isBlack()) {
rotate(newNode, newNode.parent);
rotate(newNode.parent.parent, newNode.parent.parent.rightChild);
recolor(newNode.parent);
}
}
}
}
else if(newNode.parent.leftChild == newNode){
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.leftChild.isBlack()) {
rotate(newNode, newNode.parent);
rotate(newNode.parent.parent, newNode.parent.parent.leftChild);
recolor(newNode.parent);
}
}
}
}
}
// Case 3 same condition making rotation.
if (!newNode.isBlack()){
if (newNode.parent.rightChild == newNode) {
if (!newNode.parent.isBlack()) {
if (newNode.parent.parent.isBlack()) {
if(newNode.parent.parent.leftChild == newNode.parent) {
if (newNode.parent.parent.rightChild.isBlack()) {
rotate(newNode.parent.parent, newNode.parent.parent.rightChild);
recolor(newNode.parent);
}
}
}
}
}
else if (newNode.parent.leftChild == newNode){
if (!newNode.parent.isBlack()) {
if(newNode.parent.parent.rightChild == newNode.parent) {
if (newNode.parent.parent.isBlack()) {
if (newNode.parent.parent.leftChild.isBlack()) {
rotate(newNode.parent.parent, newNode.parent.parent.leftChild);
recolor(newNode.parent);
}
}
}
}
}
}
// Case 4 same as 1 but coloring
if (!newNode.isBlack()){
if(newNode.parent.leftChild == newNode) {
if (!newNode.parent.isBlack()){
if(newNode.parent.parent.leftChild == newNode.parent){
if(newNode.parent.parent.isBlack()){
if(!newNode.parent.parent.rightChild.isBlack()){
newNode.parent.color = "Black";
newNode.parent.parent.color = "Red";
newNode.parent.parent.rightChild.color = "Black";
recolor(newNode.parent.parent);
}
}
}
}
}
else if (newNode.parent.rightChild == newNode){
if(newNode.parent.parent.rightChild == newNode.parent){
if(!newNode.parent.color.isBlank()){
if(!newNode.parent.parent.leftChild.isBlack()){
newNode.parent.color ="Black";
newNode.parent.parent.color = "Red";
newNode.parent.parent.leftChild.color = "Black";
recolor(newNode.parent.parent);
}
}
}
}
}
}
}


}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
Java Program: You will be traversing through an integer tree to print the data. Given main(),...
Java Program: You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is: 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 -...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
This is in java and you are not allowed to use Java API classes for queues,...
This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them. You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below Your code should have a menu driven user interface at the command line with...
You will be traversing through an integer tree to print the data. Given main(), write the...
You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 - 85 -...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
For this question, consider the following class which will be used to construct binary trees. Use...
For this question, consider the following class which will be used to construct binary trees. Use the convention that there is no "empty tree"; each node points to the nodes containing it's two children; and if a node has no left or right child, then the corresponding pointer will be set to null public class TreeNode { public double root; public TreeNode left; public TreeNode right; } Draw a diagram for what a tree of this model would look like...
In this code, I build a single-linked list using a node class that has been created....
In this code, I build a single-linked list using a node class that has been created. How could I change this code to take data of type T, rather than int. (PS: ignore the fact that IOHelper.getInt won't work for the type T... ie second half of main). Here's my code right now: public class SLList { public SLNode head = null; public SLNode tail = null; public void add(int a) {// add() method present for testing purposes SLNode newNode...
Using the following definition for a BST node: class BTNode { public: int data; BTNode *left;...
Using the following definition for a BST node: class BTNode { public: int data; BTNode *left; BTNode *right; BTNode(int d,BTNode *l=nullptr,BTNode *r=nullptr) :data(d),left(l),right(r) {} }; Implement a function to calculate the balance factor of a node in a BST. The function prototype must match the following function: int balance_factor(BTNode *subtree) { // IMPLEMENT return -2; } You may implement other functions to help you. In particular, you may want to implement a function to calculate a node's height. //C++ #include...