make Node and RBTree two .java plz // jus not use recursive and no sorting alfor
ID: 3802623 • Letter: M
Question
make Node and RBTree two .java plz // jus not use recursive and no sorting alforithms
For this assignment, you will be implementing a version of a Red-Black Tree. Your Red-Black tree will be implemented as a Map where each node will store a key (which must be unique) and a value. You must implement your Tree to be generic (keys can be any type that is a subclass of Comparable, and the value can be any type). You are not allowed to use any sorting algorithms in your implementation.
The Node Class
Your node class should include member variables for the key and value you want to store in the node as well as member variables which are pointers to the left and right subtrees, and the parent of the node.
You will also want to keep track of the color of the node.
Add any additional methods / constructors you feel will help. If you are unsure of your design you MUST talk to me ahead of time for approval.
The RBTree Class
The RBTree class should have a member variable that points to the root node of the entire tree.
The RBTree class should have a constant member variable Node with a value of null for its key, null for its value, and all of its pointers are also null. This will be your special NIL leaf that is required of the RBTree. This special node should only have one instantiation in memory
Add whatever constructors you feel are necessary.
You will want to include the following functionality:a way to find the grandparent of any given node
remember to check for cases where a node might not have a grandparent.
a way to find the uncle of any given node
remember to check for cases where a node might not have an uncle.
a left rotate function
remember to update the parent pointer of each node that changes
remember to connect the correct node back into the tree after the rotation
a right rotate function
remember to update the parent pointer of each node that changes
remember to connect the correct node back into the tree after the rotation
a function to start the insertion process of a new node. (most likely a helper method that calls other methods.)
a function the performs a normal binary search tree insertion (this will be used by your insert method)
a function which checks to see if the tree violates any of the rules of a RB tree and makes the necessary corrections
this will be used by your insert method
add functions for all of the traversals. these functions should return an ArrayList of Nodes in the correct order. you should also incorporate these into your gui (have buttons that can show the results of each traversal).
NOTE: You must implement these WITHOUT using recursion.
preorder: HINT: You will need to use a Stack to implement preorder nonrecursively. Research how to use the Stack class in Java.
inorder: HINT: You will need to use a Stack to implement inorder nonrecursively. Research how to use the Stack class in Java.
postorder: HINT: You will need to use a Stack and a Set to implement postorder nonrecursively. The Set will store nodes that have already been visited. Also you will need to keep track of if you are returning from the left or right subtree.
breadth-first: HINT: You will need to use a Queue to implement breadth-first. Research how to use a Queue in Java.
add any other functionality you feel is necessary.
Explanation / Answer
import java.util.Scanner;
/* Class Node */
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 count number of nodes */
public int countNodes()
{
return countNodes(header.right);
}
private int countNodes(RedBlackNode r)
{
if (r == nullNode)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
/* 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 inorder traversal */
public void inorder()
{
inorder(header.right);
}
private void inorder(RedBlackNode r)
{
if (r != nullNode)
{
inorder(r.left);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
inorder(r.right);
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(header.right);
}
private void preorder(RedBlackNode r)
{
if (r != nullNode)
{
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
preorder(r.left);
preorder(r.right);
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(header.right);
}
private void postorder(RedBlackNode r)
{
if (r != nullNode)
{
postorder(r.left);
postorder(r.right);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
}
}
}
/* 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);
System.out.println("Red Black Tree Test ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" Red Black Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
rbt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ rbt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ rbt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ rbt.isEmpty());
break;
case 5 :
System.out.println(" Tree Cleared");
rbt.makeEmpty();
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
rbt.postorder();
System.out.print(" Pre order : ");
rbt.preorder();
System.out.print(" In order : ");
rbt.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
--------------------------------------------------------------------------------
Output:
Red Black Tree Test
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
4
Empty status = true
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
8
Post order : 8B
Pre order : 8B
In order : 8B
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
3
Post order : 3R 8B
Pre order : 8B 3R
In order : 3R 8B
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
5
Post order : 3R 8R 5B
Pre order : 5B 3R 8R
In order : 3R 5B 8R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
2
Post order : 2R 3B 8B 5B
Pre order : 5B 3B 2R 8B
In order : 2R 3B 5B 8B
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
1
Post order : 1R 3R 2B 8B 5B
Pre order : 5B 2B 1R 3R 8B
In order : 1R 2B 3R 5B 8B
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
9
Post order : 1R 3R 2B 9R 8B 5B
Pre order : 5B 2B 1R 3R 8B 9R
In order : 1R 2B 3R 5B 8B 9R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
10
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
3
Nodes = 7
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
4
Search result : false
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
6
Search result : false
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
3
Search result : true
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
5
Tree Cleared
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
y
Red Black Tree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
4
Empty status = true
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.