Java中的紅黑樹規則實施

我試圖在Java中實現紅黑樹。爲了做到這一點，我允許每個插入發生，就好像它是一個BST，然後後插入我的預訂遍歷樹，並檢查每個節點（我稱爲一個字，因爲我用它字典應用程序）紅黑規則得到滿足。到目前爲止，它看起來像這樣Java中的紅黑樹規則實施

private void checkRedBlackRules(Word w) 
    { 

     //Checking for Red-Red sequence 
     Word leftChild = w.getLeft(); 
     Word rightChild = w.getRight(); 
     Word leftleftGC, leftrightGC, rightleftGC, rightrightGC; 
     if(leftChild != null) 
     { 
      leftleftGC = leftChild.getLeft(); 
      leftrightGC = leftChild.getRight(); 
     } 
     else 
     { 
      leftleftGC = null; 
      leftrightGC = null; 
     } 
     if(rightChild != null) 
     { 
      rightleftGC = rightChild.getLeft(); 
      rightrightGC = rightChild.getRight(); 
     } 
     else 
     { 
      rightleftGC = null; 
      rightrightGC = null; 
     } 
     try 
     { 
      if(leftChild.isRed() && leftleftGC.isRed()) 
      { 
       rotateRight(w, leftChild, leftleftGC); 
      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(leftChild.isRed() && leftrightGC.isRed()) 
      { 

      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(rightChild.isRed() && rightleftGC.isRed()) 
      { 

      } 
     } 
     catch(NullPointerException e) {} 
     try 
     { 
      if(rightChild.isRed() && rightrightGC.isRed()) 
      { 
       rotateLeft(w, leftChild, leftrightGC); 
      } 
     } 
     catch(NullPointerException e) {} 
     if(w.getLeft() != null) 
      checkRedBlackRules(w.getLeft()); 
     if(w.getRight() != null) 
      checkRedBlackRules(w.getRight()); 
    } 

    private void rotateLeft(Word parent, Word child, Word grandChild) 
    { 
     child = parent; 
     child.setLeft(parent); 
     child.setRight(grandChild); 
    } 
    private void rotateRight(Word parent, Word child, Word grandChild) 
    { 
     child = parent; 
     child.setLeft(grandChild); 
     child.setRight(parent); 
    }

然而，當我嘗試兩個以上的元素添加到它陷在一個無限循環，直到發生StackOverflow的錯誤樹。

來源

2015-03-18 Nick Gilbert

爲什麼你不分青紅皁白地捕捉和忽略'NullPointerException's？這是_definitely_不是正確的做法。 – 2015-03-18 23:16:14

旋轉函數看起來很奇怪......'child = parent; child.setLeft（parent）;'就像說'parent.setLeft（parent）;'。 – Alan 2015-03-18 23:18:59

沒有通過所有詳細的邏輯走，在旋轉功能不正確時，對我說：

private void rotateLeft(Word parent, Word child, Word grandChild) 
{ 
    child = parent; 
    child.setLeft(parent); 
    child.setRight(grandChild); 
}

孩子不使用參數，而不是立即設置爲父。這意味着當你調用child.setLeft（parent）時，你將原始父親的左子設置爲它自己，我相信這是造成無限循環（因此導致堆棧溢出）的原因。

來源

2015-03-18 23:23:30 Alan

Java中的紅黑樹規則實施

回答

相關問題