Question

In: Computer Science

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.
}


}

Solutions

Expert Solution

import static java.lang.Integer.max;

// Class for performing

// RBTree operations

public class RbTree {

    TreeNode Root = null;

    // Function to calculate

    // the height of the tree

    int HeightT(TreeNode Root)

    {

        int lefth, righth;

        if (Root == null

            || (Root.children == null

                && Root.children[1] == null)) {

            return 0;

        }

        lefth = HeightT(Root.children[0]);

        righth = HeightT(Root.children[1]);

        return (max(lefth, righth) + 1);

    }

    // Function to check if

    // dir is equal to 0

    int check(int dir)

    {

        return dir == 0 ? 1 : 0;

    }

    // Function to check if a

    // node's color is red or not

    boolean isRed(TreeNode Node)

    {

        return Node != null

            && Node.color.equals("R");

    }

    // Function to perform

    // single rotation

    TreeNode SingleRotate(TreeNode Node,

                          int dir)

    {

        TreeNode temp

            = Node.children[check(dir)];

        Node.children[check(dir)]

            = temp.children[dir];

        temp.children[dir] = Node;

        Root.color = "R";

        temp.color = "B";

        return temp;

    }

    // Function to perform double rotation

    TreeNode DoubleRotate(TreeNode Node,

                          int dir)

    {

        Node.children[check(dir)]

            = SingleRotate(Node.children[check(dir)],

                           check(dir));

        return SingleRotate(Node, dir);

    }

    // Function to insert a new

    // node with given data

    TreeNode Insert(RbTree tree,

                    String data)

    {

        if (tree.Root == null) {

            tree.Root

                = new TreeNode(data);

            if (tree.Root == null)

                return null;

        }

        else {

            // A temporary root

            TreeNode temp = new TreeNode("");

            // Grandparent and Parent

            TreeNode g, t;

            TreeNode p, q;

            int dir = 0, last = 0;

            t = temp;

            g = p = null;

            t.children[1] = tree.Root;

            q = t.children[1];

            while (true) {

                if (q == null) {

                    // Inserting root node

                    q = new TreeNode(data);

                    p.children[dir] = q;

                }

                // Sibling is red

                else if (isRed(q.children[0])

                         && isRed(q.children[1])) {

                    // Recoloring if both

                    // children are red

                    q.color = "R";

                    q.children[0].color = "B";

                    q.children[1].color = "B";

                }

                if (isRed(q) && isRed(p)) {

                    // Resolving red-red

                    // violation

                    int dir2;

                    if (t.children[1] == g) {

                        dir2 = 1;

                    }

                    else {

                        dir2 = 0;

                    }

                    // If children and parent

                    // are left-left or

                    // right-right of grand-parent

                    if (q == p.children[last]) {

                        t.children[dir2]

                            = SingleRotate(g,

                                           last == 0

                                               ? 1

                                               : 0);

                    }

                    // If they are opposite

                    // childs i.e left-right

                    // or right-left

                    else {

                        t.children[dir2]

                            = DoubleRotate(g,

                                           last == 0

                                               ? 1

                                               : 0);

                    }

                }

                // Checking for correct

                // position of node

                if (q.data.equals(data)) {

                    break;

                }

                last = dir;

                // Finding the path to

                // traverse [Either left

                // or right ]

                dir = q.data.compareTo(data) < 0

                          ? 1

                          : 0;

                if (g != null) {

                    t = g;

                }

                // Rearranging pointers

                g = p;

                p = q;

                q = q.children[dir];

            }

            tree.Root = temp.children[1];

        }

        // Assign black color

        // to the root node

        tree.Root.color = "B";

        return tree.Root;

    }

    // Print nodes at each

    // level in level order

    // traversal

    void PrintLevel(TreeNode root, int i)

    {

        if (root == null) {

            return;

        }

        if (i == 1) {

            System.out.print("| "

                             + root.data

                             + " | "

                             + root.color

                             + " |");

            if (root.children[0] != null) {

                System.out.print(" "

                                 + root.children[0].data

                                 + " |");

            }

            else {

                System.out.print(" "

                                 + "NULL"

                                 + " |");

            }

            if (root.children[1] != null) {

                System.out.print(" "

                                 + root.children[1].data

                                 + " |");

            }

            else {

                System.out.print(" "

                                 + "NULL"

                                 + " |");

            }

            System.out.print(" ");

            return;

        }

        PrintLevel(root.children[0],

                   i - 1);

        PrintLevel(root.children[1],

                   i - 1);

    }

    // Utility Function to

    // perform level order

    // traversal

    void LevelOrder(TreeNode root)

    {

        int i;

        for (i = 1;

             i < HeightT(root) + 1;

             i++) {

            PrintLevel(root, i);

            System.out.print("\n\n");

        }

    }

}

// Class for representing

// a node of the tree

class TreeNode {

    // Class variables

    String data, color;

    TreeNode children[];

    public TreeNode(String data)

    {

        // Color R- Red

        // and B - Black

        this.data = data;

        this.color = "R";

        children

            = new TreeNode[2];

        children[0] = null;

        children[1] = null;

    }

}

// Driver Code

class Driver {

    public static void main(String[] args)

    {

        // Tree Node Representation

        // -------------------------------------------

        // DATA | COLOR | LEFT CHILD | RIGHT CHILD |

        // -------------------------------------------

        RbTree Tree = new RbTree();

        String Sentence, Word;

        Sentence = "old is gold";

        String Word_Array[]

            = Sentence.split(" ");

        for (int i = 0;

             i < Word_Array.length;

             i++) {

            Tree.Root

                = Tree.Insert(Tree,

                              Word_Array[i]);

        }

        // Print Level Order Traversal

        System.out.println("The Level"

                           + "Order Traversal"

                           + "of the tree is:");

        Tree.LevelOrder(Tree.Root);

        System.out.println("\nInserting a"

                           + " word in the tree:");

        Word = "forever";

        Tree.Root = Tree.Insert(Tree,

                                Word);

        System.out.println("");

        Tree.LevelOrder(Tree.Root);

    }

}

The LevelOrder Traversalof the tree is:
| is | B | gold | old | 

| gold | R | NULL | NULL | | old | R | NULL | NULL | 


Inserting a word in the tree:

| is | B | gold | old | 

| gold | B | forever | NULL | | old | B | NULL | NULL | 

| forever | R | NULL | NULL |

venereology answered 8 months ago
Next > < Previous

Related Solutions

Add a generic Node class to the Java project. In the class Declare the fields using...
Add a generic Node class to the Java project. In the class Declare the fields using the generic type parameter, follow the book specification Define the accessor method getLink( ) Define the constructor, follow the book implementation Note: at the definition the name of the constructor is Node, however every time you use it as a type must postfix the generic type like Node<T> Define the addNodeAfter( ) method as explained in the PP presentation, use the generic type as...
public class MyLinked {    static class Node {        public Node (double item, Node...
public class MyLinked {    static class Node {        public Node (double item, Node next) { this.item = item; this.next = next; }        public double item;        public Node next;    }    int N;    Node first;     // remove all occurrences of item from the list    public void remove (double item) {        // TODO    } Write the remove function. Do NOT add any fields to the node/list classes, do...
public class SinglyLikedList {    private class Node{        public int item;        public...
public class SinglyLikedList {    private class Node{        public int item;        public Node next;        public Node(int item, Node next) {            this.item = item;            this.next = next;        }    }       private Node first;    public void addFirst(int a) {        first = new Node(a, first);    } } 1. Write the method add(int item, int position), which takes an item and a position, and...
Give an example of an inner and outer class. (Java)
Give an example of an inner and outer class. (Java)
Java program to implement circular linked list. public class CircularLinkedList { private Node tail; private int...
Java program to implement circular linked list. public class CircularLinkedList { private Node tail; private int size; public CircularLinkedList() { tail= null; size = 0; } public int size(){ return size; } public boolean isEmpty() { return size==0; } //if list is not empty return the first element public E first() { if (isEmpty()) return null; //code here return 0; } //if list not empty return last element public E last() { if (isEmpty()) return null; return tail.getElement(); } /*...
USING JAVA: Complete the following class. input code where it says //TODO. public class BasicBioinformatics {...
USING JAVA: Complete the following class. input code where it says //TODO. public class BasicBioinformatics { /** * Calculates and returns the complement of a DNA sequence. In DNA sequences, 'A' and 'T' are * complements of each other, as are 'C' and 'G'. The complement is formed by taking the * complement of each symbol (e.g., the complement of "GTCA" is "CAGT"). * * @param dna a char array representing a DNA sequence of arbitrary length, * containing only...
Please add comments to this code! JAVA Code: import java.text.NumberFormat; public class Item {    private...
Please add comments to this code! JAVA Code: import java.text.NumberFormat; public class Item {    private String name;    private double price;    private int bulkQuantity;    private double bulkPrice;    /***    *    * @param name    * @param price    * @param bulkQuantity    * @param bulkPrice    */    public Item(String name, double price, int bulkQuantity, double bulkPrice) {        this.name = name;        this.price = price;        this.bulkQuantity = bulkQuantity;        this.bulkPrice = bulkPrice;   ...
Complete the following Customer class below. Also, add the equals method that would compare each field....
Complete the following Customer class below. Also, add the equals method that would compare each field. Please pay attention to the format of the equals method as it needs to have the same format as shown below. public class Customer {       private int id; //customer id       private String name; //customer's name       private int discount; //discount rate in percent             //construct a new customer       public Customer(int id, String name, int discount) {                    }      ...
class nodeType                    // class used to implement a node { public:         int data;   &n
class nodeType                    // class used to implement a node { public:         int data;                        // data member of node         nodeType * next;        // pointer member of node }; int main() {         int x;         nodeType * head =________ ;                     // initialize head pointer         nodeType * tail = _______ ;                        // initialize tail pointer _______ * p;                                                 // create an auxiliary pointer to a node         for (x = 0; x < 10; ++x)         {                 p =   _________ nodeType; // create a node ___________ = x + 10;                                // store...
Please add comments to this code! JAVA code: import java.util.ArrayList; public class ShoppingCart { private final...
Please add comments to this code! JAVA code: import java.util.ArrayList; public class ShoppingCart { private final ArrayList<ItemOrder> itemOrder;    private double total = 0;    private double discount = 0;    ShoppingCart() {        itemOrder = new ArrayList<>();        total = 0;    }    public void setDiscount(boolean selected) {        if (selected) {            discount = total * .1;        }    }    public double getTotal() {        total = 0;        itemOrder.forEach((order) -> {            total +=...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT