****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. PLEASE MAKE THIS COMPATIBLE WITH RUN CONFIGURATION ARGUMENTS: INPUT.TXT AND OUTPUT.TXT

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-extends 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

The Following Might help to implement Red-Balck Tree.Use the logic from the given solution and try to implement accordingly....

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package redblacktreetest;
import java.util.*;
/**
*
* @author Pravin Roy
*/
class RedBlackNode
{   
RedBlackNode left, right;
int element;
int color;

/* Constructor */
public RedBlackNode(int theElement)
{
this( theElement, null, null );
}
/* Constructor */
public RedBlackNode(int theElement, RedBlackNode lt, RedBlackNode rt)
{
left = lt;
right = rt;
element = theElement;
color = 1;
}   
}

/* Class RBTree */
class RBTree
{
private RedBlackNode current;
private RedBlackNode parent;
private RedBlackNode grand;
private RedBlackNode great;
private RedBlackNode header;   
private static RedBlackNode nullNode;
/* static initializer for nullNode */
static
{
nullNode = new RedBlackNode(0);
nullNode.left = nullNode;
nullNode.right = nullNode;
}
/* Black - 1 RED - 0 */
static final int BLACK = 1;   
static final int RED = 0;

/* Constructor */
public RBTree(int negInf)
{
header = new RedBlackNode(negInf);
header.left = nullNode;
header.right = nullNode;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return header.right == nullNode;
}
/* Make the tree logically empty */
public void makeEmpty()
{
header.right = nullNode;
}
/* Function to insert item */
public void insert(int item )
{
current = parent = grand = header;
nullNode.element = item;
while (current.element != item)
{   
great = grand;
grand = parent;
parent = current;
current = item < current.element ? current.left : current.right;
// Check if two red children and fix if so   
if (current.left.color == RED && current.right.color == RED)
handleReorient( item );
}
// Insertion fails if already present
if (current != nullNode)
return;
current = new RedBlackNode(item, nullNode, nullNode);
// Attach to parent
if (item < parent.element)
parent.left = current;
else
parent.right = current;   
handleReorient( item );
}
private void handleReorient(int item)
{
// Do the color flip
current.color = RED;
current.left.color = BLACK;
current.right.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.right.color = BLACK;
}   
private RedBlackNode rotate(int item, RedBlackNode parent)
{
if(item < parent.element)
return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) : rotateWithRightChild(parent.left) ;  
else
return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) : rotateWithRightChild(parent.right);  
}
/* Rotate binary tree node with left child */
private RedBlackNode rotateWithLeftChild(RedBlackNode k2)
{
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
/* Rotate binary tree node with right child */
private RedBlackNode rotateWithRightChild(RedBlackNode k1)
{
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
/* Functions to search for an element */
public boolean search(int val)
{
return search(header.right, val);
}
private boolean search(RedBlackNode r, int val)
{
boolean found = false;
while ((r != nullNode) && !found)
{
int rval = r.element;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for preorder traversal */
public void preorder()
{
preorder(header.right);
}
private void preorder(RedBlackNode r)
{
char c = ' ';
if (r != nullNode)
{
if(r.color==1)
c='*';
else if (r.color == 0)
c = ' ';
System.out.print(r.element +""+c+" ");
preorder(r.left);
preorder(r.right);
}
}
}

/* Class RedBlackTreeTest */
public class RedBlackTreeTest
{
public static void main(String[] args)
{   
Scanner scan = new Scanner(System.in);
/* Creating object of RedBlack Tree */
RBTree rbt = new RBTree(Integer.MIN_VALUE);
/* Perform tree operations */
System.out.println(" Red Black Tree Operations ");
System.out.println("Integer ");
int choice;
do
{
System.out.print(" 1.Insert 2.print the tree 3.Search 3.Exit ");
System.out.print("Enter Option of peration:");
int ch=scan.nextInt();
switch(ch)
{
case 1:System.out.print("insert: ");
rbt.insert( scan.nextInt() );
break;
case 2:System.out.print("Print tree:");
rbt.preorder();
break;
case 3:System.out.print("Enter Value:");
int val=scan.nextInt();
boolean find=rbt.search(val);
System.out.println(find);
break;
}
System.out.println("Do want continue:(1=YES,0=NO)");
choice=scan.nextInt();
  
}while(choice!=0);
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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