在红黑树中,当旋转时,您需要知道谁是特定节点的父节点。但是,该节点仅具有对右子或左子的引用。
我想给一个节点实例变量“父级”,但正是出于这个原因,我认为这样做不值得,而且每次旋转更改父级引用也太复杂了。
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
所以,我的解决方案是编写 findParent() 方法,使用搜索来查找父级。我想知道是否有其他方法可以找到节点的父节点?
我的解决方案:
样本树:
50
/ \
25 75
如果你想找到节点 25 的父节点,你可以传递如下内容:
Node parent = findParent(Node25.value);
它返回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;
}
}
}