1

考虑一个二叉搜索树，其中所有键都是唯一的。节点没有父指针。
我们有多达 n/2 个标记的节点。
我可以在 O(n 2 ) 时间删除所有这些（使用后序遍历，当遇到标记节点时，在 O(n) 处删除每个）。但这是不合适的。我需要一种算法来在O(n)时间删除所有标记的节点。谢谢。

编辑删除后，我需要保持节点顺序不变。
EDIT-2所以看起来我已经使用典型的删除删除了每个标记的节点（在左子树中找到最右边的节点并将其与要删除的节点交换）。

4

3 回答 3

6

有很多方法，但这里有一个应该很容易正确，并给你一个完美平衡的树作为副作用。但是，它需要线性的额外空间。

  1. 创建一个大小为 N 减去标记节点数的数组（或 N，如果您不知道标记了多少并且不想检查它）。
  2. 将元素按顺序放置在数组中，通过中序遍历，跳过标记的元素。这需要线性时间，并且堆栈空间与树的高度成正比。
  3. 使用数组自上而下重建树。数组中的中间元素成为新的根，左子数组的中间元素成为新的左子元素，右子数组的中间元素成为新的右子子元素。递归地重复。这需要线性时间和对数堆栈空间。

更新：忘了说跳过标记的元素，但这很明显，对吧？;)

于 2012-05-08T15:34:01.183 回答
2

我已经找到了怎么做！

  • 我们使用中序遍历。
  • 我们在函数的递归调用之前检查是否需要删除节点。
  • 当我们找到要删除的节点时，我们将标记 toFindMax 并在左子树中搜索最右边的节点。
  • 如果我们遇到另一个要删除的节点，我们会将所有变量推送到堆栈并在节点被删除时弹出它们。
  • 当我们在左子树中找到最大值时，我们保存对它和它的父节点的引用。
    然后，当我们递归返回要删除的初始节点时，我们将其删除（与最大值交换）。 
static class LinearDeletion {

    public static Node MIN_VALUE = new Node(Integer.MIN_VALUE);;
    boolean toFindMax = false;
    Node parentOfMax = null;
    Node max = MIN_VALUE;
    Stack<Object> stack = new Stack<>();

    public void perform(Node x, Node parent) {

        if (x.isToDelete) {
            stack.push(toFindMax);
            stack.push(parentOfMax);
            stack.push(max);

            toFindMax = true;
            parentOfMax = null;
            max = MIN_VALUE;

            if (x.left != null) {
                perform(x.left, x);
            }


            if (x.left == null) { //deletion of the node
                if (parent.left == x) {
                    parent.left = x.right;
                } else {
                    parent.right = x.right;
                }
            } else {
                if (x.right == null) {
                    if (parent.left == x) {
                        parent.left = x.left;
                    } else {
                        parent.right = x.left;
                    }
                } else {
                    x.key = max.key;
                    x.isToDelete = max.isToDelete;
                    if (parentOfMax != x) {
                        parentOfMax.right = max.left;
                    } else {
                        x.left = max.left;
                    }
                }
            } // end of deletion
            max = (Node) stack.pop();
            parentOfMax = (Node) stack.pop();
            toFindMax = (boolean) stack.pop();
            if (toFindMax) { // check if the current node is the maximum
                if (x.key > max.key) {
                    max = x;
                    parentOfMax = parent;
                }
            }

            if (x.right != null) {
                perform(x.right, x);
            }

        } else {

            if (x.left != null) {
                perform(x.left, x);
            }

            if (toFindMax) {
                if (x.key > max.key) {
                    max = x;
                    parentOfMax = parent;
                }
            }

            if (x.right != null) {
                perform(x.right, x);
            }
        }
    }
}
于 2012-05-09T13:26:37.980 回答
1

我不明白为什么后序遍历会是 O(n 2 )。之所以删除单个节点是O(n)，是因为需要遍历树才能找到节点，这是一个O(n)的操作。但是一旦你找到一个节点，它可以在 O(1) 时间内被删除。*因此，您可以在 O(n) 时间内在一次遍历中删除所有 O(n) 标记的节点。

*除非你需要保持平衡的树。但是，您没有将其列为要求。

编辑正如@njlarsson 在他的评论中正确指出的那样，即使在找到节点之后，删除操作通常也不是 O(1)。但是，由于在访问要删除的节点之前已经遍历了左右子树，因此在子树遍历期间可以免费获得子树的最小（或最大）元素。这启用了 O(1) 删除。

于 2012-05-08T15:22:35.687 回答