紅黑樹實現空指針異常

Question

我想實現使用教科書僞代碼的RBT，但我得到一個空指針異常。我試圖添加對空值的檢查，但它只是在另一個地方的另一個空值處崩潰。我的猜測是，我不應該有這麼多的空檢查開始（否則僞代碼會反映）。無論如何，下面是我的代碼相關部分。我想感謝所有幫助我能得到至少縮小的問題：

public class RBtree { 

    public static Node root; //root of RBT 

    private class Node{ 
     private String key; //an identifying field inducing a total ordering 
     private Node left; //left child (may be NULL) 
     private Node right; //right child (may be NULL) 
     private Node parent; //parent node (NULL for root) 
     private String color; 

     //constructor 
     public Node(String key){ 
      this.key = key; 
      left = null; 
      right = null; 
      color = "red"; 

     } 

    } 

    public void addNode(String word){ 
     Node toInsert = new Node(word); 
     Node parent = null; 
     Node current = root; 
     while(current != null){ 
      //System.out.println("root = " + root + " current = " + current); 
      parent = current; 
      if(toInsert.key.compareTo(current.key) > 0){ 
       current = current.left; 
      }else{ 
       current = current.right; 
      } 
     } 
     toInsert.parent = parent; 
     if(parent == null){ 
      root = toInsert; 
     }else if(toInsert.key.compareTo(parent.key) > 0){ 
      parent.left = toInsert; 
     }else{ 
      parent.right = toInsert; 
     } 
     toInsert.left = null; 
     toInsert.right = null; 
     toInsert.color = "red"; 
     RBinsertFixUp(toInsert); 

    } 

    public void RBinsertFixUp(Node toFix){ 
     Node parent = null; 
     while(toFix.parent.color.equals("red")){ //CRASH NULL POINTER 
      if(toFix.parent.equals(toFix.parent.parent.left)){ 
       parent = toFix.parent.parent.right;  
       if(parent != null){ 
        // begin case#1 
        if(parent.color.equals("red")){ 
         toFix.parent.color = "black"; 
         parent.color = "black"; 
         toFix.parent.parent.color = "red"; 
         toFix = toFix.parent.parent; 
        } //end case#1 
        else if(toFix.equals(toFix.parent.right)){ 
         toFix = toFix.parent; //case#2 
         leftRotate(toFix.parent.parent); //case#2 
        } 
        toFix.parent.color = "black"; //case#3 
        toFix.parent.parent.color = "red"; //case#3 
        rightRotate(toFix.parent.parent); //case#3 
       } 
      } 
      else{ 
       parent = toFix.parent.parent.left;  
       if(parent != null){ 
        // begin case#1 
        if(parent.color.equals("red")){ 
         toFix.parent.color = "black"; 
         parent.color = "black"; 
         toFix.parent.parent.color = "red"; 
         toFix = toFix.parent.parent; 
        } //end case#1 
        else if(toFix.equals(toFix.parent.left)){ 
         toFix = toFix.parent; //case#2 
         leftRotate(toFix.parent.parent); //case#2 
        } 
        toFix.parent.color = "black"; //case#3 
        toFix.parent.parent.color = "red"; //case#3 
        rightRotate(toFix.parent.parent); //case#3 
       } 

      } 

     } 
     root.color = "black"; 
    } 
    // left rotation 
    public void leftRotate(Node toRotate){ 
     Node parent = toRotate.right; //set parent 
     toRotate.right = parent.left; // turn parent's left subtree into toRotate's right subtree 
     if(parent.left != null){ 
      parent.left.parent = toRotate; 
     } 
     parent.parent = toRotate.parent; // link toRotate's parent to parent 
     if(toRotate.parent == null){ 
      root = parent; 
     } 
     else if(toRotate.equals(toRotate.parent.left)){ 
      toRotate.parent.left = parent; 
     } 
     else{ 
      toRotate.parent.right = parent; 
     } 
     parent.left = toRotate; // put toRotate on parent's left 
     toRotate.parent = parent; 
    } 

    // right rotation 
    public void rightRotate(Node toRotate){ 
     Node parent = toRotate.left; //set parent 
     toRotate.left = parent.right; // turn parent's right subtree into toRotate's left subtree 
     if(parent.right != null){ 
      parent.right.parent = toRotate; 
     } 
     parent.parent = toRotate.parent; // link toRotate's parent to parent 
     if(toRotate.parent == null){ 
      root = parent; 
     } 
     else if(toRotate.equals(toRotate.parent.right)){ 
      toRotate.parent.right = parent; 
     } 
     else{ 
      toRotate.parent.left = parent; 
     } 
     parent.right = toRotate; // put toRotate on parent's right 
     toRotate.parent = parent; 
    } 

} 

主類：

public class RBtreeTester { 

    static String dictionaryName = "dictionary.txt"; 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     RBtree testerTree = new RBtree(); 

     testerTree.addNode("hello"); 
     testerTree.addNode("bye"); 
     testerTree.addNode("hi"); 
     testerTree.addNode("goodbye"); 
     testerTree.addNode("goodmorning"); 
     testerTree.addNode("goodevening"); 

    } 

} 

堆棧跟蹤：從堆棧

Exception in thread "main" java.lang.NullPointerException 
    at RBtree$Node.access$8(RBtree.java:10) 
    at RBtree.RBinsertFixUp(RBtree.java:53) 
    at RBtree.addNode(RBtree.java:47) 
    at RBtreeTester.main(RBtreeTester.java:13) 

Answer 1

調試代碼單獨走線更難而不是調試你已經添加了print statements的代碼。在提交程序（如果它是作業）或運送它（如果它是工作作品）之前，你只需要記得刪除它們。

在這種情況下，我認爲堆棧跟蹤具有所有你需要的信息。如果您插入的節點是新的根節點，當您調用RBinsertFixUp時，其parent的parent將爲NULL，並且RBinsertFixUp試圖執行的第一件事是訪問節點的父節點的方法。這將導致Java以NullPointerException異常退出。

你說得對，由非常有經驗的程序員編寫的Java代碼往往會減少檢查NULL。這不僅是算法的一個特點，那是因爲他們已經練習了通過NULL運行他們的代碼的確切位置，並知道只在那裏放置檢查。