In: Computer Science
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.
}
}
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 |