Red Black Trees

creating a class for your tree nodes, then creating another class for your Red Black Tree.

Create a file called Rbt$.$java. Inside this file, put the following:

Create a class called RbtNode that has the following fields:

$1$ Fields $-$ data $$ Stores the information in the node. This should be a simple int and should be

private.

$2$ color $$ This stores the color of the node, either red or black. This should be a single byte

$($not int$)$ and should be private.

$$ CL$\_$RED $$ This needs to be a class variable $($not instance variable$)$ and should be marked as a

public constant. It should be equal to the number $0$ and must be used to represent

a color of red for the node. The datatype should match that of the color field $($i$.$e$.$ a

byte$).$

$$ Use this by assigning the color field to CL$\_$RED.

o CL$\_$BLACK

$$ Same as CL$\_$RED, yet this is used to show the node is black. The value of this

constant should be $1.$

o left

$$ Pointer to the left child. Should be private.

o right

$$ Pointer to the right child. Should be private.

o parent

$$ Pointer to the parent. Should be private

$$ This will help out greatly for the rotations but you have to make sure you keep this

up to date for all nodes if it changes. An operation may succeed once, but if a

parent pointer isn$$t updated that should have been, the next operation may fail.

$$ Methods

o Constructor

$$ Only parameter is the data to put into the node. Should set all fields to a

reasonable initial value.

o Accessors

$$ All private fields should be given an accessor

$2$

o Mutators

$$ All private fields should be given a mutator

o Helper methods

$$ You might find creating methods such as getUncle, getGrandParent, and

others to be very helpful. Feel free to create whatever helper methods you need.

$$ A rule of thumb is that if you find yourself doing something more than once to a

node $($for example, finding a node$$s uncle$),$ then you really should make it a public

helper method on the node. This will make your logic A LOT cleaner and easier to

understand and will overall make this assignment easier.

Create a class $($in the same file$)$ called Rbt that has the following:

$$ Fields

o public field called root that points to the root of the tree. This must be public for the

visualization to work.

o Any other fields you need

$$ Public methods

o A default constructor $($i$.$e$.$ a constructor that doesn't take any parameters$).$ This will initialize

root to null.

o insert$($value$)$

$$ Takes an int as input and inserts it into the logical place in the tree $($using the same

rules as a normal Binary Search Tree$).$

$$ It will then check and solve any Red Black Tree violations. This can either be done in a

separate function that is called from insert or done in the insert function itself. I

recommend a separate function since then you can recursively call it $($remember

some cases require you to recursively call the function that detects and fixes

violations$).$

o search$($value$)$

$$ This method takes an int as input and returns true if the given value is in the tree,

false otherwise. You don't have to return the location in the tree, just a boolean

indicating whether the value is found.

$$ If root is null, you should return false $($since the value could not be found$)$

o min$()$

$$ Returns the smallest value in the tree.

$$ If the root is null, return $-1$

o max$()$

$$ Returns the largest value in the tree.

$$ If the root is null, return $-1.$

o size$()$

$$ Returns the number of nodes in the tree.

$$ If the root is null, return $0.$

$3$

o inorder$()$

$$ Performs an inorder traversal. $$ Does NOT print anything

$$ Instead, this returns a string with each node value $($in order$)$ with a single space

between values. You are allowed to have a single leading and$/$or a single trailing space

if you like.

$$ You must use recursion here

$$ Hint: making a local variable for the string you are creating might not be a good idea.

Consider making a field for this instead

$$ This function does NOT take any parameters, but feel free to create another function

to help with the recursion.

Duplicate Values:

Do not worry about handling duplicate values. You can safely assume that I will not attempt to store the

same value twice in your tree, so your tree does not have to handle this situation.

for maiin part

Rbt tree $=$ new Rbt$()$;

$//$ load it up with some initial values

tree.insert$(5)$;

tree.insert$(15)$;

tree.insert$(2)$;

$//$ test it out

while $($true$)\{$

Vis.showTree$($tree$)$;

if $(!$Vis.showMenu$($tree$))\{$

break;

$\}$

$\}$

This will allow you to take your Rbt object and show it on the screen $($in beautiful ASCII art fashion$).$ It

will also display a menu wherein you can test out any operation you want. All the operations you must

implement are able to be tested here. Typing quit$()$ will exit the application $($i$.$e$.$ this means

Vis.showMenu$($tree$)$ will return false and the loop above will exit.$)$

Rubric:

$1$ insert method $2$ search method $3$ min method $4$ max method $5$ size method $6$ inorder method $7$ uses Vis correctly for visualization