在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）時間從二元搜索樹中刪除多個節點

回答

相關問題