Red Black Tree Реализация Null Pointer Exception

Question

Я пытаюсь реализовать RBT с использованием псевдокода учебников, но я получаю исключение нулевого указателя. Я попробовал добавить проверки на null, но он просто падает с другим нулем куда-то дальше. Я предполагаю, что у меня не должно быть так много нулевых проверок для начала (иначе псевдокод мог бы это отразить). Во всяком случае, ниже мои соответствующие части кода. Я бы признателен за любую помощь я могу получить по крайней мере, сужая проблему:

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; 
    } 

} 

MAIN класс:

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"); 

    } 

} 

StackTrace:

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. Вам просто нужно убрать их, прежде чем отправлять программу (если это домашняя работа) или отправить ее (если это будет работа).

В этом случае, я думаю, что трассировка стека имеет всю необходимую информацию. Если вставленный вами узел является новым корневым узлом, его parent будет NULL, когда вы позвоните RBinsertFixUp, и первое, что пытается сделать, - это получить доступ к методу родительского узла. Это приведет к выходу Java с помощью исключения NullPointerException.

И вы правы, код Java, написанный очень опытными программистами, имеет меньше проверок для NULL. Однако это не просто особенность алгоритма; это потому, что они практиковали мышление именно там, где можно встретить NULL, запуская свой код, и знаете, что там только чеки.