我正在尝试用Java实现红黑树。 为此，我允许每个插入发生就像它是BST然后插入后我预先遍历树并检查每个节点（我称之为Word，因为我将它用于字典应用程序）红黑规则得到满足。 到目前为止它看起来像这样
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错误。
I'm trying to implement a Red-Black Tree in Java. To do this, I'm allowing each insert to happen as if it were a BST and then post-insert I pre-order traverse the tree and check each Node (which I call a Word as I'm using it for a dictionary application) that the Red-Black Rules are satisfied. So far it looks like this
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); }However, when I try to add more than two elements to the tree it gets stuck in an endless loop until a StackOverflow error occurs.
最满意答案
没有详细介绍所有逻辑，旋转函数对我来说看起来不正确：
private void rotateLeft(Word parent, Word child, Word grandChild) { child = parent; child.setLeft(parent); child.setRight(grandChild); }不使用child参数，而是立即将其设置为父参数。 这意味着当你调用child.setLeft（parent）时，你将原始父级的左子项设置为自身，我认为这是导致无限循环的原因（因此堆栈溢出）。
Without going through all of the logic in detail, the rotate functions look incorrect to me:
private void rotateLeft(Word parent, Word child, Word grandChild) { child = parent; child.setLeft(parent); child.setRight(grandChild); }The child parameter is not used, and is instead immediately set to the parent. This means that when you call child.setLeft(parent), you're setting the original parent's left child to itself, which I believe is what is causing an infinite loop (and therefore the stack overflow).
更多推荐
发布评论