In red-black tree, when rotate, you need to know who is the parent of particular node. However, the node only has reference to either right or left child.
I was thinking to give a node instance variable "parent" but just for this reason I don't think it is worth doing so and also it would be too complicated to change parent reference per rotation.
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
So, my solution is to write findParent() method that use search to find parent. I am wondering if there is any other way to find a node's parent?
My solution:
sample tree:
50
/ \
25 75
If you want to find parent of Node 25, you pass something like:
Node parent = findParent(Node25.value);
and it returns node50.
protected Node findParent(int val) {
if(root == null) {
return null;
}
Node current = root;
Node parent = current;
while(true) {
if(current.val == val) { //found
return parent;
}
if(current == null) { //not found
return null;
}
parent = current;
if(current.val > val) { //go left
current = current.left;
}
else { //go right
current = current.right;
}
}
}