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中的红黑树规则实施

回答

相关问题