Java 中的红黑树规则执行

Question

我正在尝试在 Java 中实现红黑树。为此，我允许每个插入都像 BST 一样发生，然后 post-insert 我预先遍历树并检查每个节点（我在使用它时称之为 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);
    }

但是，当我尝试向树中添加两个以上的元素时，它会陷入无限循环，直到发生 Whosebug 错误。

Answer 1

在我没有仔细研究所有逻辑的情况下，旋转函数看起来不正确：

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

未使用子参数，而是立即设置为父参数。这意味着当您调用 child.setLeft(parent) 时，您将原始父级的左子级设置为其自身，我认为这是导致无限循环（因此堆栈溢出）的原因。

Java 中的红黑树规则执行

Red Black Tree Rule Enforcement in Java

java

tree

red-black-tree