Question: Hello, the following code. In LeftRotaate and RightRotate methods for all occurrences of parent, it errors indicating that parent cannot be resolved or not a
Hello, the following code. In LeftRotaate and RightRotate methods for all occurrences of "parent", it errors indicating that "parent cannot be resolved or not a filed". Can you help me to correct this.
public boolean insert(int i) {
if(root == null) {
root = new Node(i, Color.BLACK);
return true;
}
Stack
Node node = root;
while(node != NIL) {
if(i == node.data) {
return false; // duplicate value
}
stack.push(node);
if(i < node.data) {
node = node.left;
} else {
node = node.right;
}
}
Node parent = stack.peek();
Node newNode = new Node(i, Color.RED);
if(i < parent.data) {
parent.left = newNode;
} else {
parent.right = newNode;
}
insertFixup(newNode, stack);
return true;
}
private void insertFixup(Node node, Stack
Node parent, grandParent, uncle;
while(node.color == Color.RED && (parent = stack.pop()).color == Color.RED) {
grandParent = stack.empty() ? null : stack.peek();
if(grandParent == null) {
node.color = Color.BLACK;
} else {
uncle = grandParent.left == parent ? grandParent.right : grandParent.left;
if(uncle.color == Color.RED) {
parent.color = uncle.color = Color.BLACK;
grandParent.color = Color.RED;
node = grandParent;
} else {
if(parent.right == node && grandParent.left == parent) {
leftRotate(parent);
node = parent;
parent = node.left;
} else if(parent.left == node && grandParent.right == parent) {
rightRotate(parent);
node = parent;
parent = node.right;
}
parent.color = Color.BLACK;
grandParent.color = Color.RED;
if(parent.left == node && grandParent.left == parent) {
rightRotate(grandParent);
} else {
leftRotate(grandParent);
}
}
}
}
root.color = Color.BLACK;
}
void leftRotate(Node node) {
Node parent = node.right;
node.right = parent.left;
if(parent.left != NIL) {
parent.left = node.right;
}
if(node != root) {
if(node == node.parent.left) {
node.parent.left = parent;
} else {
node.parent.right = parent;
}
} else {
root = parent;
}
parent.left = node;
node.parent = parent;
}
private void rightRotate(Node node) {
Node parent = node.left;
node.left = parent.right;
if(parent.right != NIL) {
parent.right.parent = node;
}
if(node != root) {
if(node == node.parent.right) {
node.parent.right = parent;
} else {
node.parent.left = parent;
}
} else {
root = parent;
}
parent.right = node;
node.parent = parent;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help