For the following RedBlackTree how would you build a Search Method utilizing strings in Java? I try and use this search method but it doesn't seem to work if the item isn't in the tree... I attempt to use this but it doesn't seem to work... if I do redBlackTree.insert("F"); //then BinNode foundNode = redBlackTree.search("L"); //or some item not in the RBT System.out.println("Node found: " + foundNode.getData()); //I get an error "Cannot invoke "BinNode.getData()" because "foundNode" is null" what would I need to modify in BinNode to get this working? public BinNode search(String val) { return search(this.getRoot(), val); } /* Function to search for an element recursively */
For the following RedBlackTree how would you build a Search Method utilizing strings in Java? I try and use this search method but it doesn't seem to work if the item isn't in the tree...
I attempt to use this but it doesn't seem to work... if I do
redBlackTree.insert("F");
//then
BinNode foundNode = redBlackTree.search("L"); //or some item not in the RBT
System.out.println("Node found: " + foundNode.getData());
//I get an error "Cannot invoke "BinNode.getData()" because "foundNode" is null" what would I need to modify in BinNode to get this working?
public BinNode search(String val)
{
return search(this.getRoot(), val);
}
/* Function to search for an element recursively */
private BinNode search(BinNode r, String val)
{
// Base case: If the current node is null, the value is not found.
if (r == null) {
return null;
}
int comparison = val.compareTo(r.getData());
if (comparison < 0) {
// Value is smaller, so search in the left subtree.
return search(r.getLeft(), val);
} else if (comparison > 0) {
// Value is larger, so search in the right subtree.
return search(r.getRight(), val);
} else {
// Value is equal to the current node's data, so it's found.
//this.curr = r;
return r;
}
}
public class RedBlackTree extends BinaryTree{
private BinNode root;
private BinNode nil;
public RedBlackTree() {
nil = new BinNode();
nil.setColor(false); // Black color for NIL nodes
root = nil;
}
public BinNode getRoot() {
return this.root;
}
public void insert(String data) {
BinNode newNode = new BinNode(data);
newNode.setColor(true); // New nodes are always red
newNode.setLeft(nil);
newNode.setRight(nil);
BinNode y = null;
BinNode x = this.root;
while (x != nil) {
y = x;
int comparison = data.compareTo(x.getData());
if (comparison < 0) {
x = x.getLeft();
} else {
x = x.getRight();
}
}
newNode.setParent(y);
if (y == null) {
this.root = newNode; // Tree was empty
} else if (data.compareTo(y.getData()) < 0) {
y.setLeft(newNode);
} else {
y.setRight(newNode);
}
insertFixup(newNode);
}
private void insertFixup(BinNode z) {
while (z.getParent() != null && z.getParent().getColor()) {
if (z.getParent() == z.getParent().getParent().getLeft()) {
BinNode y = z.getParent().getParent().getRight();
if (y.getColor()) {
z.getParent().setColor(false);
y.setColor(false);
z.getParent().getParent().setColor(true);
z = z.getParent().getParent();
} else {
if (z == z.getParent().getRight()) {
z = z.getParent();
leftRotate(z);
}
z.getParent().setColor(false);
z.getParent().getParent().setColor(true);
rightRotate(z.getParent().getParent());
}
} else {
BinNode y = z.getParent().getParent().getLeft();
if (y.getColor()) {
z.getParent().setColor(false);
y.setColor(false);
z.getParent().getParent().setColor(true);
z = z.getParent().getParent();
} else {
if (z == z.getParent().getLeft()) {
z = z.getParent();
rightRotate(z);
}
z.getParent().setColor(false);
z.getParent().getParent().setColor(true);
leftRotate(z.getParent().getParent());
}
}
}
this.root.setColor(false);
}
private void leftRotate(BinNode x) {
if (x.getParent() != null) {
BinNode y = x.getRight();
x.setRight(y.getLeft());
if (y.getLeft() != nil) {
y.getLeft().setParent(x);
}
y.setParent(x.getParent());
if (x.getParent() == nil) {
this.root = y;
} else if (x == x.getParent().getLeft()) {
x.getParent().setLeft(y);
} else {
x.getParent().setRight(y);
}
y.setLeft(x);
x.setParent(y);
}
}
private void rightRotate(BinNode x) {
if (x.getParent() != null) {
BinNode y = x.getLeft();
x.setLeft(y.getRight());
if (y.getRight() != nil) {
y.getRight().setParent(x);
}
y.setParent(x.getParent());
if (x.getParent() == nil) {
this.root = y;
} else if (x == x.getParent().getRight()) {
x.getParent().setRight(y);
} else {
x.getParent().setLeft(y);
}
y.setRight(x);
x.setParent(y);}}
private BinNode minimum(BinNode x) {
while (x.getLeft() != nil) {
x = x.getLeft();
}return x;}
public void display() {
display(root);}
private void display(BinNode node) {
if (node != null) {
display(node.getLeft());
System.out.print(node.getData() + " ");
display(node.getRight());
}
}
private void transplant(BinNode u, BinNode v) {
if (u.getParent() == nil) {
this.root = v;
} else if (u == u.getParent().getLeft()) {
u.getParent().setLeft(v);
} else {
u.getParent().setRight(v);
}
v.setParent(u.getParent());
}
}
Step by step
Solved in 5 steps
