2
빨간색 - 검은 색 트리에서 회전 할 때 특정 노드의 부모가 누구인지 알아야합니다. 그러나 노드에는 오른쪽 또는 왼쪽 자식에 대한 참조 만 있습니다.레드 - 블랙 트리 - 노드의 부모를 찾는 방법?
나는 노드 인스턴스 변수에 "parent"를 주려고했으나 이런 이유 때문에 그렇게할만한 가치가 있다고 생각하지 않으며 회전 당 부모 참조를 변경하기에는 너무 복잡 할 것이라고 생각합니다.
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
그래서 제 해결책은 검색을 사용하여 부모를 찾는 findParent() 메소드를 작성하는 것입니다. 노드의 부모를 찾는 다른 방법이 있다면 궁금합니다.
내 솔루션 :
샘플 나무 : 당신은 노드 (25)의 부모를 찾으려면
50
/\
25 75
, 당신은 같은 것을 통과 :
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;
}
}
}
내가 틀릴 수도 있지만 일반적인 방법은 호출 스택의 매개 변수로 부모를 회전 함수로 전달하는 것입니다. – mikera
libavl을 살펴 봐야합니다. 올바른 방법은 검색 할 때 조상을 스택에 보관하는 것입니다. – user172818