Größten Eintrag aus Binärbaum löschen

[Alpinwhite]

Hallo, kann mir jemand helfen diese Methode nachzuvollziehen:
Sie soll den größten Eintrag eines Binärbaums löschen.

Ich verstehe das so:
-1. Es wird in der ersten if-Schleife überprüft ob die Baumwurzel null ist. Falls ja soll null zurückgegeben werden.
2. Falls eine Wurzel existiert wird In der zweiten if-Schleife wird überprüft ob rechts überhaupt etwas ist. Falls nein ist automatisch der linke Wert der Größte. Ergibt noch Sinn.
3. Dann kommt das was ich nicht ganz verstehe: Falls rechts doch ein Wert existiert (also in die else-Anweisung übergegangen wird, soll

else
p.right = delMaxR(p.right);
return p;

das hier gelten. Na gut.. Man ruft die Methode rekursiv nochmal auf und übergibt p.right, was aber meiner Meinung nach darin resultiert, dass irgendwann die erste if-Schleife greift, da p ja irgendwann null sein muss. Demnach wird einfach nur null zurückgegeben irgendwann ?

public void delMax()
{
root = delMaxR(root);
}
private static Node delMaxR(Node p)
{
if (p == null)
return null;
if (p.right == null)
p
= p.left;
else
p.right = delMaxR(p.right);
return p;
}

 

[mihe7]

p ist nur dann null, wenn beim ersten Aufruf von delMaxR null übergeben wurde. Danach wird nämlich geprüft, ob p.right null ist.

EDIT: Deine Annahme, dass im else-Zweig irgendwann delMaxR(null) aufgerufen werden könnte, ist falsch. Denn dann wäre p.right == null und dieser Fall wird im then-Zweig behandelt.

 

[Alpinwhite]

Hallo, danke soweit.

Ich dachte eigentlich dass beim erneuten Methodenaufruf das p.right, das übergeben wird dann als "p" gehandelt wird.

 

[mihe7]

Ja, so ist es ja auch.

 

[Meniskusschaden]

Falls nein ist automatisch der linke Wert der Größte. Ergibt noch Sinn.

Nein, dann enthält die Wurzel den größten Wert. Deshalb wird sie auch entfernt.