Das maximale Element in BST löschen

Question

Einige der unten aufgeführten Code scheint zu offensichtlich, durchqueren den Baum mit seinem rechten Zweig, da das ist, wo alle maximalen Werte sind. Allerdings verstehe ich ein paar Dinge über diesen Code ich nicht sah in Robert Sedgewicks Algorithms Buch.

 public void deleteMax() { 
    if (isEmpty()) throw new NoSuchElementException(""); 
    root = deleteMax(root); 
    assert check(); 
    } 

    private Node deleteMax(Node x) { 
    if (x.right == null) return x.left; 
    x.right = deleteMax(x.right); 
    x.size = size(x.left) + size(x.right) + 1; 
    return x; 
    } 

Im privaten Methode, warum wir das linke Element tun zurück, wenn das rechte Kind von x null ist? Von meinem Verständnis x das Maximum wäre, wenn x keine richtigen Kinder und ist die am weitesten rechts stehenden Knoten wir gehen könnten zu. Auch ich verstehe nicht, wann wir x in der letzten Zeile der 2. Methode zurückgeben.

Answer 1

Wenn x kein rechtes Kind hat, dann ist x der maximale Knoten. Wir "löschen" es, indem wir x.left (der neue maximale Knoten) zurückgeben. Wir geben x zurück, nachdem wir den rechten Teilbaum geändert haben.