在O（n）时间从二元搜索树中删除多个节点

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

编辑删除后，我需要有节点顺序不变。
EDIT-2因此，它应该看起来像我已删除每个标记的节点使用典型的删除（找到左子树的最右边的节点，并与节点交换删除）。在O（n）时间从二元搜索树中删除多个节点

来源

2012-05-08 Temak

你是什么意思的“节点订单不变”？目前给出的答案都假定二叉搜索树的正常左右键顺序应该被保留。你的意思是说没有节点应该有比以前更多的父节点吗？如果一个有标记的孩子有两个没有标记的孩子，这是不可能实现的。 – njlarsson

我发现如何做到这一点！

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

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-09 13:26:37 Temak

我不明白为什么后序遍历是O（n ）。删除单个节点的原因是O（n）是您需要遍历树来查找节点，这是一个O（n）操作。但是一旦找到一个节点，它就可以在O（1）时间内被删除。因此，您可以在O（n）时间内在单个遍历中删除所有标记为O（n）的节点。

^*除非你需要保持一个平衡的树。但是，您不会将其列为要求。

编辑正如@njlarsson在他的评论中正确指出的，即使在找到节点之后，删除操作通常不是O（1）。然而，由于在访问要删除的节点之前正在遍历左右子树，所以在子树遍历期间可以在不额外花费的情况下获得子树的最小（或最大）元素。这使O（1）删除成为可能。

来源

2012-05-08 15:22:35

找到它后，您无法在O（1）时间内删除节点。如果节点有两个子树，则必须将它们合并为一个。标准方法（在非平衡树中）是交换节点以删除左子树中的最大元素（或最小值在右子树中），但这需要到达树的底部，这可能是线性的在不平衡的树中。 – njlarsson

@njlarsson - 好点。我想这个问题很容易解决。可以定义后序遍历来返回最小（或最大）节点。然后，当一个节点被访问时，右边子树中的最小值（或左边子树中的最大值）将立即可用，以免节点需要被删除。 –

是的，应该可以工作，但只有在每个节点都有一个指向其父节点的指针时，因为您还需要修改父节点的最大值/最小值。如果不这样做，那可以通过某种方式来解决，但它变得越来越复杂。 – njlarsson

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

创建大小为N减标节点的数量的数组（或N，如果你不知道有多少被标记，不要检查它做）。
按顺序放置元素，按顺序遍历，跳过标记元素。这需要线性时间，并且堆栈空间与树的高度成比例。
使用数组重建树自上而下。数组中的中间元素成为新的根，左侧子数组的中间元素为其新左侧子元素，右侧子数组的中间元素为其新子右侧子元素。重复递归。这需要线性时间和对数栈空间。

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

来源

2012-05-08 15:34:01 njlarsson

在O（n）时间从二元搜索树中删除多个节点

回答

相关问题