在java中的RedBlackTree插入实现

我想实现红黑树的CLRS伪代码。当我试图运行该程序时，会抛出NullPointerException。请检查代码并找出它有什么不对。欢迎任何进一步的建议。在java中的RedBlackTree插入实现

public class RedBlackTree { 

Node nil; 
Node root; 
String RED = "red"; 
String BLACK = "black"; 

public void left_rotate(RedBlackTree T, Node x) { 
    Node y = x.right; 
    x.right = y.left; 
    if (y.left != T.nil) 
     y.left.parent = x; 
    y.parent = x.parent; 
    if (x.parent == T.nil) 
     T.root = y; 
    else if (x == x.parent.left) 
     x.parent.left = y; 
    else 
     x.parent.right = y; 
    y.left = x; 
    x.parent = y; 
} 

public void right_rotate(RedBlackTree T, Node x) { 
    Node y = x.left; 
    x.left = y.right; 
    if (y.right != T.nil) 
     y.right.parent = x; 
    y.parent = x.parent; 
    if (x.parent == T.nil) 
     T.root = y; 
    else if (x == x.parent.right) 
     x.parent.right = y; 
    else 
     x.parent.left = y; 
    y.right = x; 
    x.parent = y; 
} 

public void rb_insert_fixup(RedBlackTree T, Node z) { 

    while (z.parent.color == RED) { 
     if (z.parent == z.parent.parent.left) { 
      Node y = z.parent.parent.right; 
      if (y.color == RED) { 
       z.parent.color = BLACK; 
       y.color = BLACK; 
       z.parent.parent.color = RED; 
       z = z.parent.parent; 
      } else { 
       if (z == z.parent.right) { 
        z = z.parent; 
        left_rotate(T, z); 
       } 
       z.parent.color = BLACK; 
       z.parent.parent.color = RED; 
       right_rotate(T, z.parent.parent); 
      } 
     } else { 
      Node y = z.parent.parent.left; 
      if (y.color == RED) { 
       z.parent.color = BLACK; 
       y.color = BLACK; 
       z.parent.parent.color = RED; 
       z = z.parent.parent; 
      } else { 
       if (z == z.parent.left) { 

        z = z.parent; 
        right_rotate(T, z); 
       } 
       z.parent.color = BLACK; 
       z.parent.parent.color = RED; 
       left_rotate(T, z.parent.parent); 
      } 
     } 

    } 
    T.root.color = BLACK; 
} 

public void insert(RedBlackTree T, Node z) { 
    Node y = T.nil; 
    Node x = T.root; 
    while (x != T.nil) { 
     y = x; 
     if (z.key < x.key) 
      x = x.left; 
     else 
      x = x.right; 
    } 
    z.parent = y; 
    if (y == T.nil) 
     T.root = z; 
    else if (z.key < y.key) 
     y.left = z; 
    else 
     y.right = z; 
    z.left = T.nil; 
    z.right = T.nil; 
    z.color = RED; 
    rb_insert_fixup(T, z); 
} 

public void inorder_tree_walk(Node x) { 
    if (x != null) { 
     inorder_tree_walk(x.left); 
     System.out.println(x.key + ":" + x.color + " "); 
     inorder_tree_walk(x.right); 
    } 
} 

public static void main(String[] args) { 
    RedBlackTree rbt = new RedBlackTree(); 

    Node a = new Node(12, "a"); 
    rbt.insert(rbt, a); 
    Node b = new Node(5, "b"); 
    rbt.insert(rbt, b); 
    Node c = new Node(18, "c"); 
    rbt.insert(rbt, c); 
    Node d = new Node(2, "d"); 
    rbt.insert(rbt, d); 
    Node e = new Node(9, "e"); 
    rbt.insert(rbt, e); 

    rbt.inorder_tree_walk(rbt.root); 
    } 

} 

class Node { 
int key; 
String data; 
String color; 
Node left, right, parent; 

public Node(int key, String data) { 
    this.key = key; 
    this.data = data; 
    } 
}

堆栈跟踪是：在RedBlackTree.rb_insert_fixup（RedBlackTree.java:42）在RedBlackTree.insert（RedBlackTree.java:102在螺纹

异常 “主” 显示java.lang.NullPointerException ）在RedBlackTree.main（RedBlackTree.java:117）

来源

2015-10-19 aditya

请通过此http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception-and-how -do-i-fix-it看看你是否可以修复，如果没有，那么你可以请添加完整的stacktrace –

谢谢。但我找不到这个错误。作为答案之一，建议Node nil和root需要初始化。但即使在那之后，它仍然抛出NullPointerException.Can你请帮忙吗？ – aditya

你可以提供你从哪里引用红黑树的CLRS伪代码的链接..bcoz我试图运行你的程序，发现很多例外...即使我给你修复上述stackTrace异常它会给你另一个异常bcoz你没有正确实施插入代码。 –

必须初始化nil和root：

public class RedBlackTree { 

Node nil; <-- is null 
Node root; <-- is null

否则，这也是空：

while (z.parent.color == RED) { <-- z.parent is null

来源

2015-10-19 07:21:29 KostasC

即使在我初始化nil和root为null之后，它仍然会抛出NullPointerException。 – aditya

我得到了错误。这是因为我没有初始化无节点和根节点。我在零节点和空节点之间感到困惑。现在我明白了。代码中有一个小错误。纠正这些错误后，程序正常运行。谢谢求助。 – aditya

@aditya很乐意为您效劳！ – KostasC

在java中的RedBlackTree插入实现

回答

相关问题