紅黑樹刪除根

我的紅黑樹算法刪除效果很好，除非我刪除根。哪裏只有一個孩子被保存，其餘的樹值都丟失。紅黑樹刪除根

我相信這個問題是在

下面是用於刪除方法的線removeNode()方法：

//Searching for value to remove 
public void removeSearch(int value) 
{ 
    RedBlackNode rt = root; 
    while (rt != sentinel) 
    { 
     int compare = value.CompareTo(rt.getItem()); 
     if (compare == 0) 
     { 
      if (rt.getLeft() == sentinel || rt.getRight() == sentinel) 
      { 
       removeNode(rt); 
      } 
      else 
      { 
       RedBlackNode successor = inOrderSuccessor(rt); 
       rt.setItem(successor.getItem()); 
       removeNode(rt);       
      } 
      return; 
     } 
     else 
     { 
      rt = rt.getChild(compare); 
      //return true; 
     } 
    } 
} 

protected RedBlackNode inOrderSuccessor(RedBlackNode node) 
{ 
    RedBlackNode descendant = node.getRight(); 

     while (descendant.getLeft() != sentinel) 
     { 
      descendant = descendant.getLeft(); 
     } 
    return descendant; 
} 

protected void removeNode(RedBlackNode remove) 
{ 
    count -= 1; 
    RedBlackNode child; 
    if (remove.getLeft() != sentinel) 
    { 
     child = remove.getLeft(); 
    } 
    else 
    { 
     child = remove.getRight(); 
    } 
    linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent())); 

    if(remove==root) 
    { 
     root = child; 
    } 
    if(remove.isBlack()) 
    { 
     DeleteFix(child); 
    } 
} 

protected void DeleteFix(RedBlackNode node) 
{ 
    while((node!=root)&&(node.isBlack())) 
    { 
     RedBlackNode parent = node.getParent(); 
     int compare = comparison(node, parent); 
     RedBlackNode sibling = parent.getChild(-compare); 
     if(sibling.isRed()) 
     { 
      sibling.setBlack(); 
      parent.setRed(); 
      rotate(-compare, parent); 
      sibling = node.getParent().getChild(-compare); 
     } 
     if(sibling.hasTwoBlackChildren()) 
     { 
      sibling.setRed(); 
      node = node.getParent(); 
     }else 
     { 
      if(sibling.getChild(-compare).isBlack()) 
      { 
       sibling.getChild(compare).setBlack(); 
       sibling.setRed(); 
       rotate(compare, sibling); 
       sibling = parent.getChild(-compare); 
      } 
      sibling.setColour(parent.getColour()); 
      parent.setBlack(); 
      sibling.getChild(-compare).setBlack(); 
      rotate(-compare, parent); 
      node = root; 
     } 
    } 
    node.setBlack(); 
}

任何幫助將是巨大的。由於

來源

2016-04-12 Techworld

走過這跟我說：

if (remove.getLeft() != sentinel) 
{ 
    child = remove.getLeft(); 
} 
else 
{ 
    child = remove.getRight(); 
} 
linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent())); 

if(remove==root) 
{ 
    root = child; 
}

首先，假設remove == root。然後，假設根的左孩子是sentinel。第一個if分支的計算結果爲false，將執行else子句，並且child將成爲正確的節點。然後，你嘗試獲取根的父（大概null，但我不知道），並將其鏈接到正確的節點...我想這最終沒有做什麼，但我不知道，因爲你沒有，提供該方法。然後，您將根替換爲child（這是正確的節點），並且由於linkParentAndChild（大概）在null中被傳遞，因此無法恢復左節點，因此您將其斷開並且它消失了。如果左邊的節點不是sentinel，那麼過程是完全一樣的，但你會保留左側而不是右側。

希望這應該清除它爲什麼會發生。我不會告訴你如何解決這個問題，原因有兩個：

這幾乎可以肯定是家庭作業，沒有人實現紅黑樹，除非是作業。
我真的不記得的紅黑樹的實現細節非常好，主要是由於原因號碼1

祝你好運解決它！

來源

2016-04-12 22:43:04

是的，事實上我錯了，當我繼續調試時，根總是排除要刪除的選定節點的右側子樹。這種情況不僅發生在根 – Techworld

中，有可能提供一些需要做的事情的提示嗎？我不確定我是否錯過了我的方法中的大量信息 – Techworld

我對代碼的瞭解不夠，無法幫助您進行廣泛的調試，但聽起來像您與「sentinel」的比較不起作用。如果你沒有在'RedBlackNode'上定義一個'Equals（）'方法，它會測試引用標識（我認爲）上的相等性，所以除非你在任何地方使用完全相同的'sentinel'，否則比較可能不起作用。或者它可能是別的，我不知道。與同學談話或拜訪教練的辦公時間會更好（也更安全）。 –

紅黑樹刪除根

回答

相關問題