remove Methode
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Binärer Suchbaum
Hi,
Kann mir bitte jemand eine Zeile in der remove Methode erklären :)?
public Entry remove(E val) {
int result = val.compareTo(value);
if (result < 0) { // val < value
if (left != null) {
left = left.remove(val);
if (left != null) left.parent = this;
}
return this;
} else if (result > 0) { // val > value
if (right != null) {
right = right.remove(val);
if (right != null) right.parent = this;
}
return this;
} else { // val == value
if ((left == null) && (right == null)) return null;
else if (left == null) return right;
else if (right == null) return left;
else { // der aktuelle Knoten hat zwei Kinder
value = right.removeMin();
if (right.value == null) {
right = right.right;
if (right != null) right.parent = this;
}
return this;
}
}
}Für was benötige ich die Zeile
if (left != null) left.parent = this; ??
danke schonmal!
In der Zeile darüber wird das Löschen an das linke Kind delegiert, welches sich rekursiv um das Löschen kümmert und das Ergebnis an den Aufrufer zurückgibt. Nun kann es sein, dass das Kind selbst das zu löschende Element trägt, in welchem Fall u.U. ein anderer Baum mit neuer Wurzel zurückgegeben wird – dieser Baum ist dann das neue linke Kind und muss entsprechend auch den richtigen Vater-Verweis erhalten.
danke, jetzt ist mir das klar