В красно-черном дереве при вращении вам нужно знать, кто является родителем конкретного узла. Однако узел имеет ссылку только на правого или левого дочернего элемента.
Я думал дать переменной экземпляра узла «родительский», но только по этой причине я не думаю, что это стоит делать, а также было бы слишком сложно изменить ссылку на родительский узел за один оборот.
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
Итак, мое решение состоит в том, чтобы написать метод findParent(), который использует поиск для поиска родителя. Мне интересно, есть ли другой способ найти родителя узла?
Мое решение:
образец дерева:
50
/ \
25 75
Если вы хотите найти родителя Node 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;
}
}
}
