删除BST中的最大元素

Question

下面的一些代码似乎太明显了，使用最右边的分支遍历树，因为这是所有最大值所在的位置。然而，我在RobertSedgewick的算法书中看到的这段代码有一些地方我不太懂。

     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。

Answer 1

如果x没有正确的子节点，那么x是最大节点。我们通过返回x.left（新的最大节点）来“删除”它。我们在修改了它的右子树后返回x。