java - 更新 BST 中的删除路径

Question

我希望在这里得到一些意见。我构建了一个二维二叉搜索树类。我的所有操作(插入、删除等)都正常工作。我遇到了一个似乎无法解决的问题。我当前在每个节点中都有数据成员，必须在删除路径内更新这些数据成员(相对高度、各个子树的极值等)。问题是，我需要我的删除方法返回一个 boolean 值，表示它成功。意思是，如果节点不存在，则返回 false。否则为真。我正在递归地解决这个问题，因此当我完成每个函数调用时，我正在更新值

了解正在发生的情况，删除如下所示:

private boolean delete (Node n, Value val, boolean cut) {
   // Base case
   if(n == null) return false;
   if(node to be deleted) {
        // Do all sorts of swapping, recursive deletion calls
   }
   else {
       // Move around the tree until I find a node or hit null
       if(is in left subtree)
         delete(t.left, val, !cut);
       if(is in right subtree)
         delete(t.right, val, !cut);
   }

   // Here is where updating happens
   someUpdateFunction(n);

   // Now java here is forcing me to return something, so I have to return true or false  
   return true;
}

所以我的问题是我总是返回 true，因为这段代码总是执行。有人知道如何更新我的删除路径，并且在节点不存在时仍然能够返回 false 吗？感谢您的任何意见。

Answer 1

private boolean delete (Node n, Value val, boolean cut) {
   boolean status = false;
   // Base case
   if(n == null) return false;
   if(node to be deleted) {
        // Do all sorts of swapping, recursive deletion calls
   }
   else {
       // Move around the tree until I find a node or hit null
       if(is in left subtree){
             status = delete(t.left, val, !cut);
       }else if(is in right subtree){
             status = delete(t.right, val, !cut);
       }         
   }

   // Here is where updating happens
   someUpdateFunction(n);

   return status;
}