AVL Tree Left Rotation

Question

Я исправляю класс дерева AVL, и у меня возникают проблемы с моим методом "rotateLeft".Я получаю исключение нулевого указателя, и я не уверен, что его вызывает.Вот класс:

public class AVLNode {

// Fields
int data;
AVLNode left;
AVLNode right;
int height;

// Constructors
AVLNode (int data) {
    this(data, null, null);
}

AVLNode (int data, AVLNode left, AVLNode right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.height = 0;
}


// Returns: new root of this subtree
 public AVLNode insert (int value, AVLNode rt) {
     if (rt == null)
         return new AVLNode(value, null, null);
     if (value < rt.data)
         rt.left = insert(value, rt.left);
     else if (value > rt.data)
         rt.right = insert(value, rt.right);
     // else this is a duplicate, do nothing
     rt.height = Math.max(height(rt.left), height(rt.right)) + 1;
     return balance(rt);
 }

 // Returns : String representation of tree root at this node
 public String toString() {
     return toString(this);
 }

 // Returns : String representation of tree root at rt
 private String toString(AVLNode rt) {
     if (rt == null)
         return "";
     if (rt.left == null && rt.right == null)
         return rt.data + " ";
     String result = rt.data + " ";
     if (rt.left != null)
         result += toString(rt.left);
     if (rt.right != null)
         result += toString(rt.right);
     return result;

}

 // Returns: height of largest subtree, -1 if n is null
 private int height (AVLNode n) {
     return n == null ? -1 : n.height;
 }

 //calculates balance between the nodes
 private int getBalance(AVLNode rt) { 
     if (rt == null) return 0; 
     return height(rt.left) - height(rt.right); 
 }

 // Returns: new root of this subtree after balancing
 private AVLNode balance (AVLNode rt) {
     int bal = getBalance(rt);
     if (rt == null) return rt;

     // Rotate L case
     if (bal > 1 && data < rt.left.data) {
         return rotateRight(rt); 
     }

     // Rotate R case
     if (bal < -1 && data > rt.right.data) {
         return rotateLeft(rt); 
     }

     // Double rotate LR
     if (bal > 1 && data > rt.left.data) {
         return doubleRotateLeftRight(rt);
     } 

     // Double rotate RL
     if (bal < -1 && data < rt.right.data) {
         return doubleRotateRightLeft(rt); 
     }

     return rt;
 }

 // Returns: new root after single rotation of this rt right
 private AVLNode rotateRight(AVLNode rt) {
     //creates new node with the left value of rt as the root
     AVLNode y = rt.left;
     //creates a new node with a null value
     AVLNode rt2 = y.right; 

     // do rotation
     y.right = rt; 
     rt.left = rt2;

     //update height of both nodes
     rt.height = Math.max(height(rt.left), height(rt.right)) + 1;
     y.height =  Math.max(height(y.left), height(y.right)) + 1;

     // Return the new root 
     return y; 
 }

 // Param: AVLNode rt
 // Returns: new root after single rotation of this rt left
 private AVLNode rotateLeft(AVLNode rt) {
     //creates new node with the right values of rt as the root
     AVLNode x = rt.right;
     //creates a new node with a null value
     AVLNode rt2 = x.left; 

     // do rotation
     x.left = rt; 
     rt.right = rt2; 

     //update height of both nodes
     rt.height = Math.max(height(rt.left), height(rt.right)) + 1;
     x.height = Math.max(height(x.left), height(x.right)) + 1;

     // Return the new root 
     return x; 
 }

 private AVLNode doubleRotateLeftRight(AVLNode rt) {
     rt.left = rotateLeft(rt.left);
     rotateRight(rt);
     return rt;
 }

 private AVLNode doubleRotateRightLeft(AVLNode rt) {
     rt.right = rotateRight(rt.right);
     rotateLeft(rt);
     return rt;
 }
}

В частности, это ошибка:

Exception in thread "main" java.lang.NullPointerException
        at AVLNode.rotateRight(AVLNode.java:118)
        at AVLNode.balance(AVLNode.java:96)
        at AVLNode.insert(AVLNode.java:42)
        at AVLNode.insert(AVLNode.java:37)
         at AVLTest.main(AVLTest.java:22)

Это тестовый пример, который я использую: 60,10,61,9,8.Это когда я добавляю 8 в дерево, где я сталкиваюсь с ошибкой.Я считаю, что ошибка заключается в самом методе, но я не совсем уверен в том, что является причиной проблемы.Любая помощь будет принята с благодарностью.

Answer 1

Мне удалось выяснить проблему, метод перейдет к одному из методов двойного поворота и попытается повернуть поддерево дважды, когда в этом нет необходимости.Что объясняет исключение нулевого указателя, решение состоит в том, чтобы добавить проверку баланса для дерева в обоих методах двойного вращения.

 private AVLNode doubleRotateLeftRight(AVLNode rt) {
    if (getBalance(rt.left) < 0) {
        rt.left= rotateLeft(rt.left);
        return rotateRight(rt);
    } else {
        return rotateRight(rt);
    }
}

private AVLNode doubleRotateRightLeft(AVLNode rt) {
   if (getBalance(rt.right) > 0) {
        rt.right = rotateRight(rt.right);
        return rotateLeft(rt);
    } else {
        return rotateLeft(rt);
    }
}