在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插入實現

回答

相關問題