****PLEASE DO NOT COPY PASTE FROM OTHER CHEGG QUESTIONS**** ***PLEASE FOLLOW THE

Question

****PLEASE DO NOT COPY PASTE FROM OTHER CHEGG QUESTIONS****

***PLEASE FOLLOW THE INTRUCTIONS EXACTLY AS STATED. NOTE THAT THERE SHOULD BE FILE I/O TO DISPLAY THE FUNCTIONALITY OF THE METHODS***

THANK YOU!

The task of this project is to implement in Java a red-black tree data structure. However, the tree will be simplified you only need to support insertion, not deletion Specification The project must implement the following specification exactly, including all identifier names, method signatures, the presence or absence of exceptional behavior, etc. That being said, anything not clearly indicated by the UML diagram(s) or explicitly stated in the description is left up to your discretion. You may also add private helper methods or additional fields as necessary Structure E fextends Comparable) E (extends Comparable) RedBlackTree «static» Node «static»-RED: boolean= false -element: E -leftChild: Node rightChild: Node -parent: Node -color: boolean «static»-BLACK: boolean = true root: Node +insert(element: E): boolean throws NullPointerException +contains(object: ComparableE>): boolean +toString0: String Note that a box with a dashed border over the top right of a class entity denotes a generic type parameter. In this case, the red-black tree class has a generic type named E that extends Comparableyou may choose whether or not to make Node generic as well. The Comparable interface is located in the java.lang package, so it is not necessary to import it. Finally, for this project you should locate your code in the default package Behavion insert should insert the given element into the tree at the correct position, and then rebalance the tree if necessary. The correct position is defined by the properties of a binary search tree, and the rebalancing procedure should enforce the properties of a red-black tree. Regarding input validation, insert should immediately throw a NullPointerException with a descriptive message if the given element is null. Alternatively, if the given element is a duplicate of an element already in the tree, then insert should not insert the given element. The return value should indicate whether the given element was inserted into the tree or not Two elements are considered duplicates iff (if and only if) they compare equal to each other using the compareTo method. Likewise, the ordering of any two elements for the purposes of insertion and rebalancing is given by the same method contains should return whether the tree contains any element that compares equal to the given object using the compareTo method of the object. This means that you should always do object.compareTo (element) but never do element.compareTo (object).

Explanation / Answer

/*
* Java Program to Implement Red Black Tree
*/

import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.File;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/* Class Node */
class Node
{   
     Node leftChild, rightChild;
     int element;
     int color;

     /* Constructor */
     public Node(int theElement)
     {
         this( theElement, null, null );
     }
     /* Constructor */
     public Node(int theElement, Node lc, Node rc)
     {
         leftChild = lc;
         rightChild = rc;
         element = theElement;
         color = 1;
     }   
}

/* Class RedBlackTree */
class RedBlackTree
{
     private Node current;
     private Node parent;
     private Node grand;
     private Node great;
     private Node header;   
     private static Node nullNode;
     private String treeOutput="";
     /* static initializer for nullNode */
     static
     {
         nullNode = new Node(0);
         nullNode.leftChild = nullNode;
         nullNode.rightChild = nullNode;
     }
     /* Black - 1 RED - 0 */
     static final int BLACK = 1;   
     static final int RED   = 0;

     /* Constructor */
     public RedBlackTree(int negInf)
     {
         header = new Node(negInf);
         header.leftChild = nullNode;
         header.rightChild = nullNode;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty()
     {
         return header.rightChild == nullNode;
     }
     /* Make the tree logically empty */
     public void makeEmpty()
     {
         header.rightChild = nullNode;
     }
     /* Function to insert item */
     public void insert(int item )
     {
         if (item == -1) {
            throw new NullPointerException();
        }
        if(search(item)==false)
        {
             current = parent = grand = header;
             nullNode.element = item;
             while (current.element != item)
             {           
                 great = grand;
                 grand = parent;
                 parent = current;
                 current = item < current.element ? current.leftChild : current.rightChild;
                 // Check if two red children and fix if so           
                 if (current.leftChild.color == RED && current.rightChild.color == RED)
                     handleReorient( item );
             }
             // Insertion fails if already present
             if (current != nullNode)
                 return;
             current = new Node(item, nullNode, nullNode);
             // Attach to parent
             if (item < parent.element)
                 parent.leftChild = current;
             else
                 parent.rightChild = current;       
             handleReorient( item );
        }
     }
     private void handleReorient(int item)
     {
         // Do the color flip
         current.color = RED;
         current.leftChild.color = BLACK;
         current.rightChild.color = BLACK;

         if (parent.color == RED)  
         {
             // Have to rotate
             grand.color = RED;
             if (item < grand.element != item < parent.element)
                 parent = rotate( item, grand ); // Start dbl rotate
             current = rotate(item, great );
             current.color = BLACK;
         }
         // Make root black
         header.rightChild.color = BLACK;
     }     
     private Node rotate(int item, Node parent)
     {
         if(item < parent.element)
             return parent.leftChild = item < parent.leftChild.element ? rotateWithleftChild(parent.leftChild) : rotateWithrightChild(parent.leftChild) ;
         else
             return parent.rightChild = item < parent.rightChild.element ? rotateWithleftChild(parent.rightChild) : rotateWithrightChild(parent.rightChild);
     }
     /* Rotate binary tree node with leftChild child */
     private Node rotateWithleftChild(Node k2)
     {
         Node k1 = k2.leftChild;
         k2.leftChild = k1.rightChild;
         k1.rightChild = k2;
         return k1;
     }
     /* Rotate binary tree node with rightChild child */
     private Node rotateWithrightChild(Node k1)
     {
         Node k2 = k1.rightChild;
         k1.rightChild = k2.leftChild;
         k2.leftChild = k1;
         return k2;
     }
         /* Functions to search for an element */
     public boolean search(int val)
     {
         return search(header.rightChild, val);
     }
     private boolean search(Node r, int val)
     {
         boolean found = false;
         while ((r != nullNode) && !found)
         {
             int rval = r.element;
             if (val < rval)
                 r = r.leftChild;
             else if (val > rval)
                 r = r.rightChild;
             else
             {
                 found = true;
                 break;
             }
             found = search(r, val);
         }
         return found;
     }

   
     /* Function for preorder traversal */
     public String preorder()
     {
         preorder(header.rightChild);
         return treeOutput;
     }
     private void preorder(Node r)
     {
         if (r != nullNode)
         {
            
             if (r.color == 0)
            
               treeOutput = treeOutput + "*"+r.element+" ";
             else
                treeOutput = treeOutput + r.element+" ";
             preorder(r.leftChild);            
             preorder(r.rightChild);
         }
       
     }
    
    
}

/* Class RedBlackTreeTest */
public class RedBlackTreeTest
{
     public static void main(String[] args)
     {           
       String[] info;
       String nextLine;
       String title = "";
       String data = "";
       int valu="-1";
       System.out.println("Enter the input file path: ");
       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            // Reading file name to read
       String inputFile = reader.readLine();
      
       System.out.println("Enter the output file path: ");
       // Reading file name to write
       String outputFile = reader.readLine();
        
                /* Creating object of RedBlack Tree */
       RedBlackTree rbt = new RedBlackTree(Integer.MIN_VALUE);
       BufferedReader inFile = new BufferedReader(new FileReader(inputFile));
       BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));
      
       // read file contents
       while((nextLine = inFile.readLine()) != null)
        {
            if(nextLine.indexOf(":")!=-1")
            {
                info = nextLine.split(":");
                title = info[0];
                data = info[1];
                if(data!="")
                {
                    try
                    {
                  value = Integer.parseInt(data);
                    }
                    catch
                    {
                        thow new NullPointerException();
                    }
                }
            }
            else
            {
                title=nextLine;
            }
           
        /* Perform tree operations */
           if(title=="Insert")
           {
               try
               {
                 rbt.insert(value);
                 fwriter.write("True");
               }
               catch
                {
                  thow new NullPointerException();
                }
           }
           if(title=="PrintTree")
           {
               fwriter.write(rbt.preorder());
           }

        }
        writer.close();
        inFile.Close();

     }

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.