如何在Java中编写懒惰的已删除二进制搜索树的findMinimum [英] How to write findMinimum of a lazy deleted Binary Search Tree in Java

问题描述

我正在使用惰性删除在Java中为二叉搜索树编写一个类(不是从树中删除节点，而是将已删除"标志设置为true)

I am writing a class for a Binary Search Tree in Java that uses lazy deletion (instead of removing the node from the tree, it sets a "deleted" flag to true)

我的问题是，如何为这样的树实现findMin函数?仅转到最左边的叶子的常规方法将不起作用，因为该线索可能会被删除".

My question is, how would I implement a findMin function for a tree like this? The normal method of just going to the leftmost leaf wouldn't work because that lead may be "deleted".

例如，像这样的树，您删除20、5和17

For example, A tree like this where you delete 20, 5, and 17

         25
     *20     30
   *17        89
  *5

当您调用findMin()时应返回25.

should return 25 when you call findMin().

我的实现如下:

public int findMin() {
    return doFindMin(root);
}

private int doFindMin(TreeNode node) {
    if (node == null) {
        return -1;
    } else if (node.getLeftChild() != null) {
        return doFindMin(node.getLeftChild());
    } else if (!node.isDeleted()) {
        return node.getKey();
    } else if (node.getRightChild() != null){
        return doFindMin(node.getRightChild());
    } else return -1;
}

当我在上述情况下调用该函数时，它返回-1.如果我不删除17，它将正确返回最小值17.

When I call the function with the situation described above, it returns -1. If I don't delete 17, it correctly returns 17 as the minimum.

任何对此的帮助将不胜感激.谢谢.

Any help with this would be greatly appreciated. Thanks.

17错误地放置在树中，原始帖子已更新以解决此问题.

17 was placed incorrectly in the tree, original post has been updated to fix this problem.

推荐答案

执行未标记为已删除的有序记录节点.第一个未删除的元素是最小值.找到第一个元素后，您可以中断遍历. 您可以执行以下操作:

Do an inorder recording nodes that aren't marked as deleted. The first non-deleted element is the minimum.You could break out of traversal once you found the first one. You could do something like below:

void inOrderForMinimum( TreeNode node, int[] min ) {
    if ( node != null && min[0] == -1 ) {
       inOrderForMinimum( node.getLeftChild(), min );
       if ( !node.isDeleted() ) {
          min[0] = node.value;
       }
       inOrderForMinimum( node.getRightChild(), min );
   }
}

这样称呼:

private int findMinimum( TreeNode root ) {
   int[] min = new int[]{-1};
   inOrderForMinimum( root, min );
   return min[0];
}

这篇关于如何在Java中编写懒惰的已删除二进制搜索树的findMinimum的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！