BSTの最大要素を削除する

Question

以下のコードのいくつかはあまりにも明白です。それは右端の枝を使ってツリーを横断するので、それはすべての最大値が存在するからです。しかし、このコードについて私はいくつか理解していません。 Robert Sedgewickのアルゴリズムの本で見た。民間の方法では

 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; 
    } 

xの右の子がnullの場合、なぜ我々は左の要素を返すのですか？xは我々が行くことができる権利ほとんどのノードを権利、子供を持っていないし、ある場合は私の理解から、xが最大になります私はxを2番目の方法の最後の行にいつ返すのか分かりません。

Answer 1

xに右の子がない場合は、xが最大ノードです。我々はx.left（新しい最大ノード）を返すことによってそれを "削除"します。正しいサブツリーを修正した後、xを返します。