刪除BST中的最大元素

Question

下面的一些代碼看起來太明顯了，它使用其最右邊的分支遍歷樹，因爲這是所有最大值所在的地方。但是，我不明白關於此代碼的一些事情I在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的右子是空？從我的理解X都將是最大的，如果x無權孩子，是我們可以去最右邊的節點的私有方法to.Also我不明白什麼時候我們在第二種方法的最後一行返回x。

Answer 1

如果x沒有合適的孩子，那麼x是最大節點。我們通過返回x.left（新的最大節點）來「刪除」它。修改其右側子樹後，我們返回x。