2
В красно-черном дереве, когда вы вращаетесь, вам нужно знать, кто является родителем определенного узла. Однако узел имеет ссылку только на правый или левый дочерний элемент.Красно-черное дерево - Как найти родителя узла?
Я думал дать переменную экземпляра узла «родительский», но по этой причине я не думаю, что это стоит того, и было бы слишком сложно изменить родительскую ссылку на поворот.
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;
}
}
}
Возможно, я ошибаюсь, но я считаю, что обычный подход состоит в том, чтобы передать родительский элемент в качестве параметра в стеке вызовов функции вращения. – mikera
Вы должны посмотреть на libavl. Правильный способ - держать предков в стеке при поиске. – user172818