remove中的一些问题

Question

// 从二分搜索树中删除键为key的节点
    @Override
    public V remove(K key){

        Node node = getNode(root, key);
        if(node != null){
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key){

        if( node == null )
            return null;

       ........

老师这里的代码，如果在上面的remove中已经判断node是否为空，那么进入递归函数的条件是node不为空，为什么递归函数的其中一个终止条件还要判断新的node是否为空呢？这样不是永远不会有if(node == null)的情况出现吗？

Answer 1

liuyubobobo 2020-04-22 11:38:39

上面的 node 和下面的 node 不是一个东西。

上面的 node 是我们先找到待删除节点对应的 node，我们要确认这个待删除节点是存在的，才能进行删除。可能换个名字，叫 delNode，更清晰，是待删除节点。

但下面的 node，是函数的一个参数名，这个参数名 node 所对应的节点，是跟着我们递归过程传的参数不同而在改变的。比如，在初始点用的时候，我们调用的是 remove(root, key)，那么进入这个函数，这个 node 指的是 root。

下面函数的这个 node 在怎么变化，是理解这个删除过程的关键。我建议你实际创建一棵树，3 层就可以，然后删除一个叶子节点，使用单步跟踪的方式实际看一下，递归的 remove 函数中，node 是在怎么变化的。结合这个课程中我讲链表的递归删除的微观操作，理解一下这个过程。

加油！：）

• 提问者 Ethan_Qjm #1

  老师，我明白你的意思，上面的node和下面的node不是同一个。
  但是上面的node是我找到了那个待删除节点，而下面的函数是递归到待删除节点之后对该节点进行处理，既然上面是找到那个待删除节点才执行递归函数，那下面的递归函数就永远不会有node==null这个情况啊？而且它是私有函数，外面无法访问，那个判断那个node==null
  其实并没有用啊？不知道我这样理解有没有错？

• liuyubobobo 回复 提问者 Ethan_Qjm #2

  我理解你的意思了。我们下面实现的这个 remove，确实可以化简上面的逻辑，直接改成：
  Node delNode = remove(root, key); 
  return delNode == null ? null : delNode.value; 
  如果待删除节点不存在，delNode 直接拿到一个 null，不需要先查找：）

• 提问者 Ethan_Qjm 回复 liuyubobobo #3

  谢谢老师，其实我一开始问这个问题的时候，想的是把下面的递归函数简化，但是最后老师给我的答案是把上面的简化，老师这个比我的之前想的更好，如果像我之前想的把下面递归函数，删掉if(node == null),这样其实还没有递归到底，老师的这种写法，既不破坏递归的终止条件的完整性，还不需要先寻找待删除节点，这样也会让函数运行得更快，学到了，哈哈。再次感谢老师。

点开查看后面4条评论