試圖平衡AVL樹當添加（插入）：Java的

Question

我想後，我添加一個新的項目，以樹來平衡我的AVL樹，但我不斷收到的NPE。我相信我已經縮小了它與我的balance（）方法，或者更具體地說我的rotateLeft（）和rotateRight（）方法有關。這是我的AVLTree類：

package proj; 

import java.util.LinkedList; 
import java.util.Queue; 

public class AVLTree<T extends Comparable<T>> { 

    private Queue<Node<T>> tree; 
    private Node<T> root; 
    private int size; 

    public AVLTree(){ 
     tree = new LinkedList<Node<T>>(); 
     root = null; 
     size = 0; 
    } 

    public void add(T value){ 
     Node<T> n = new Node<T>(value); 

     if(root == null){ 
      root = n; 
      tree.add(n); 
      size++; 
     } 
     else{ 
      add(root, value); 
     } 
    } 

    //adds a new node to the tree then re-balances if necessary 
    public void add(Node<T> subtree, T value){ 
     Node<T> n = new Node<T>(value); 

     if(subtree == null){ 
      subtree = n; 

      tree.add(n); 
      size++; 
      if(size()>2){ 
       balance(n.getParent()); 
      } 
     } 
     else{ 
      int difference = subtree.getValue().compareTo(n.getValue()); 
      if(difference<0){ 
       if(subtree.getRightChild()==null){ 
        subtree.setRightChild(n); 
        n.setParent(subtree); 

        tree.add(n); 
        size++; 

        if(size()>2){ 
         balance(n.getParent()); 
        } 
       } 
       else{ 
        add(subtree.getRightChild(), value); 
       } 
      } 
      else if(difference>0){ 
       if(subtree.getLeftChild()==null){ 
        subtree.setLeftChild(n); 
        n.setParent(subtree); 

        tree.add(n); 
        size++; 
        if(size()>2){ 
         balance(n.getParent()); 
        } 
       } 
       else{ 
        add(subtree.getLeftChild(), value); 
       } 
      } 
      else if(difference==0){ 
       return; 
      } 
     } 
    } 

    //balances the tree 
    public void balance(Node<T> n){ 
     if(balanceFactor(n) == -2){ 
      if(balanceFactor(n.getRightChild())<0){ 
       rotateLeft(n); 
       if(balanceFactor(n.getRightChild())==-1){ 
        rotateLeft(n); 
        rotateLeft(n.getRightChild()); 
       } 
       else if(balanceFactor(n.getRightChild())==1){ 
        rotateRight(n.getRightChild()); 
        rotateLeft(n); 
       } 
      } 
     } 
     else if(balanceFactor(n) == 2){ 
      if(balanceFactor(n.getLeftChild())>0){ 
       rotateRight(n); 
       if(balanceFactor(n.getLeftChild())==1){ 
        rotateRight(n); 
        rotateRight(n.getLeftChild()); 
       } 
       else if(balanceFactor(n.getLeftChild())==-1){ 
        rotateLeft(n.getLeftChild()); 
        rotateRight(n); 
       } 
      } 
     } 
     if(n.getParent() != null){ 
      balance(n.getParent()); 
     } 
    } 

    //performs a left rotation on the passed 
    //subtree root 
    public void rotateLeft(Node<T> subtree){ 
     Node<T> temp = subtree.getRightChild(); 
     subtree.setRightChild(temp.getLeftChild()); 
     temp.setLeftChild(subtree); 
     subtree = temp; 
    } 

    //performs a right rotation on the passed 
    //subtree root 
    public void rotateRight(Node<T> subtree){ 
     Node<T> temp = subtree.getLeftChild(); 
     subtree.setLeftChild(temp.getRightChild()); 
     temp.setRightChild(subtree); 
     subtree = temp; 
    } 

    //returns the tree in its current state 
    public Queue<Node<T>> getTree(){ 
     return tree; 
    } 

    //returns the root of the tree 
    public Node<T> getRoot(){ 
     return root; 
    } 

    //returns the size of the tree 
    public int size(){ 
     return size; 
    } 

    //returns the head of the queue 
    public Node<T> peek(){ 
     Node<T> current = root; 
     while(current.getLeftChild() != null){ 
      current = current.getLeftChild(); 
     } 
     return current; 
    } 

    //returns the height of the tree; returns -1 if the tree is empty 
    public int height(Node<T> n){ 
     if(n == null){ 
      return -1; 
     } 
     return Math.max(height(n.getLeftChild()), height(n.getRightChild()))+ 1; 
    } 

    //returns the balance factor of the passed subtree 
    public int balanceFactor(Node<T> subtree){ 
      return height(subtree.getLeftChild()) - height(subtree.getRightChild()); 
    } 

    public static void main(String[] args){ 
     AVLTree<Integer> avl = new AVLTree<Integer>(); 
     avl.add(1); 
     avl.add(2); 
     avl.add(3); 
     avl.add(4); 
     avl.add(5); 

     System.out.println("Root: " + avl.root.getValue()); 
     System.out.println("Root's left: " + avl.root.getRightChild().getValue()); 

     System.out.println("Root's balance factor: " + avl.balanceFactor(avl.getRoot())); 
     System.out.println("Tree Size: " + avl.size()); 
     for(Node<Integer> n : avl.tree){ 
      System.out.println(n.getValue()); 
     } 
    } 
} 

我在做我錯誤地提到的方法，還是我錯誤地將樹之前，我甚至去平衡？

Answer 1

我就曾經在一段時間，直到你得到的答案編輯這樣的：

1）當AvlTree.add（）被調用，參數（空，等等）的子樹參數被替換爲全新的節點。如果樹的大小大於2，則調用balance(n.getParent())。我猜想n.getParent()在這種情況下總是會返回null。當balance()被調用時，首先完成的是balanceFactor(null)，這將導致產生NPE的線上的NPE。