红黑树-打印错误

Question

我在研究了红黑树之后尝试实现它，但是在打印红黑树时出现错误。能否请您看一下，并建议在执行红黑树插入时是否有任何错误。它只显示根，它是第一个递归的左右子节点，然后显示以下错误：

Exception in thread "main" java.lang.WhosebugError
at java.io.FileOutputStream.write(FileOutputStream.java:326)
at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
at java.io.PrintStream.write(PrintStream.java:482)
at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
at java.io.PrintStream.write(PrintStream.java:527)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)
at RedBlackTree.preOrder(RedBlackTree.java:161)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:163)

最后两行错误重复多次。

对于打印命令，我使用简单的预购递归代码。以下是代码：

public class RedBlackTree {

public RBNode root;

void leftRotate(RBNode node)
{
    RBNode y;
    y = node.right;
    if(y.left != null)y.left.parent = node;
    y.parent = node.parent;

    if(node.parent == null)root = y;
    else
    {
        if(node == node.parent.left)node.parent.left = y;
        else node.parent.right =y;
    }
    y.left = node;
    node.parent = y;
}

void rightRotate(RBNode node)
{
    RBNode y;
    y = node.left;
    if(y.right != null)y.right.parent = node;
    y.parent = node.parent;

    if(node.parent == null)root = y;
    else
    {
        if(node == node.parent.right)node.parent.right = y;
        else node.parent.left =y;
    }
    y.right = node;
    node.parent = y;
}

void insertNode(RBNode node, RBNode data)
{
    // INSERT IN ROOT
    if(node == null)
    {
        node = new RBNode(data.key);
        root = node;
        root.color = 0;
        System.out.println("Root " + root.key);

    }

    else if (data.key < node.key && node.left == null)
    {

        node.left = data;
        data.parent = node;



    }
    else if(data.key >node.key && node.right == null)
    {

        node.right  = data;
        data.parent = node;


    }

    else{
        if(data.key < node.key)insertNode(node.left, data);
        else insertNode(node.right, data);
    }

    data.color = 1;


    RBNode uncle;
    //Check REB BLACK PROPERTIES

    while(data.parent != null && data.parent.color ==1 && data != root && data.color != 0)
    {
                System.out.println("Data " + data.key + " Parent " + data.parent.key);

                //PARENT IS RIGHT CHILD
                if(data.parent == data.parent.parent.right)
                {
                    System.out.println("Parent RIGHT");
                    uncle = data.parent.parent.left; 
                    if(uncle == null) System.out.println("Uncle is null");

                    //UNCLE IS BLACK OR NULL
                    if(uncle == null || uncle.color == 0)
                    {
                        System.out.println("Uncle BLACK or NULL");
                        if(data == data.parent.left)
                        {
                            System.out.println("Node is LEFT");
                            data = data.parent;
                            rightRotate(data);
                        }
                        data.parent.color = 0;
                        if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
                        leftRotate(data.parent.parent);
                    }
                    //UNCLE IS RED
                    else
                    {
                        System.out.println("Uncle RED");
                        data.parent.parent.left.color = 0;
                        data.parent.color = 0;
                        if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
                        data = data.parent;
                    }


                }
                // PARENT IS LEFT CHILD
                else
                {
                    System.out.println("Parent LEFT");
                    uncle = data.parent.parent.right; 
                    //UNCLE IS NULL OR BLACK
                    if(uncle ==null || uncle.color == 0)
                    {
                        System.out.println("Uncle BLACK or NULL");
                        System.out.println("");
                        if(data == data.parent.right)
                        {
                            System.out.println("Node is RIGHT");
                            data = data.parent;
                            leftRotate(data);
                        }
                        data.parent.color = 0;
                        if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
                        rightRotate(data.parent.parent);    
                    }
                    //UNCLE IS RED
                    else
                    {
                        System.out.println("Uncle RED");

                        data.parent.parent.right.color = 0;
                        data.parent.color = 0;
                        if(data.parent.parent.key != root.key)data.parent.parent.color= 1;
                        data = data.parent;
                    }

                }


    }
    root.color = 0;

}

void preOrder(RBNode node)
{
    if(node != null)
    {
        System.out.println("Value : " + node.key + "Color: " + node.color);
        preOrder(node.left);
        preOrder(node.right);
    }
}

public static void main(String args[])
{
    RedBlackTree tree = new RedBlackTree();
    tree.insertNode(tree.root, new RBNode(2));
    tree.insertNode(tree.root, new RBNode(1));
    tree.insertNode(tree.root, new RBNode(4));
    tree.insertNode(tree.root, new RBNode(5));
    tree.insertNode(tree.root, new RBNode(9));
    tree.insertNode(tree.root, new RBNode(3));
    tree.insertNode(tree.root, new RBNode(6));

    tree.insertNode(tree.root, new RBNode(7));


    tree.preOrder(tree.root);
  }


}

class RBNode
{
 int key; 
 RBNode parent;
 RBNode left;
 RBNode right;
 int color;  // 1 = RED , 0 = BLACK
public RBNode(int key)
 {
    this.key = key;
    this.parent = null;
    this.left = null;
    this.right = null;


 }
}

是不是插入实现有误？

Answer 1

我能够解决那个特定的错误，所以代码仍然没有给出完整的正确答案。左右旋转实现错误，报错

void leftRotate(RBNode node)
{
    RBNode y;
    y = node.right;
    node.right = y.left;

    if(y.left != null)y.left.parent = node;

    y.parent = node.parent;

    if(node.parent == null)root = y;
    else
    {
        if(node == node.parent.left)node.parent.left = y;
        else node.parent.right =y;
    }
    y.left = node;
    node.parent = y;
}

void rightRotate(RBNode node)
{
    RBNode y;
    y = node.left;
    node.left = y.right;
    if(y.right != null)y.right.parent = node;

    y.parent = node.parent;

    if(node.parent == null)root = y;
    else
    {
        if(node == node.parent.right)node.parent.right = y;
        else node.parent.left =y;
    }
    y.right = node;
    node.parent = y;
}

红黑树-打印错误

Red Black Tree - Print Error

java

algorithm

tree

red-black-tree