java - 使用延迟删除在 BST 中硬删除节点的方法

Question

我在课堂上有一个作业，我们正在实现一个带有延迟删除的 BST。当一个节点被删除时，它只是被标记为已删除，并没有真正从树中删除。当我们想要实际硬删除树中标记为已删除的所有节点时，我们必须创建一个方法。

现在我正在使用一种方法，delete()，它沿着树递归。如果它找到一个标记为已删除的节点，它会调用 removeHard() 并在其中包含所有删除机制。我已经测试了 delete() 方法，我似乎正确地遍历了树并捕获了所有标记的节点，然后将这些节点传递给我的 removeHard() 方法。另外，当我在我的主要方法中公开调用 removeHard() 作为测试时，它会正确删除节点。结合起来，它要么根本不删除节点，要么创建重复项。

protected void delete( FHlazySTNode<E> root )
{
  if ( root == null )
     return;

  if ( root.rtChild != null )
     delete(root.rtChild);
  if (root.deleted)
     removeHard(root);
  if ( root.lftChild != null )
     delete(root.lftChild);

}

   protected FHlazySTNode<E> removeHard( FHlazySTNode<E> root )
{

  if (root == null)
     return null;

  if (root.lftChild != null && root.rtChild != null)
  {
     root.data = findMin(root.rtChild).data;
     root.deleted = findMin(root.rtChild).deleted;
     root.rtChild = removeHard(root.rtChild);
  }
  else
  {
     root =
        (root.lftChild != null)? root.lftChild : root.rtChild;
  }
  return root;
}