添加（插入）时尝试平衡 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。