Расширение внешнего узла на внутренний узел в AVLTree

Question

Я выполняю это задание AVLTree, и у меня есть проблема с методом вставки. Я получаю сообщение об ошибке, когда он добирается до z.resetHeight();

public void insert(K key, V value) { 

    AVLnode<K, V> hold = TreeSearch(key, root); 
    AVLnode<K, V> z = hold; 
    DictEntry<K, V> temp = new DictEntry<K, V>(key, value); 
    z.setEntry(temp); 

    while (z != null) { 
     z.resetHeight(); 
     if (java.lang.Math 
       .abs(z.left().getHeight() - z.right().getHeight()) > 1) { 
      z = triNodeRestructure(z.parent().parent(), z.parent(), z); 
      z.left().resetHeight(); 
      z.right().resetHeight(); 
      z.resetHeight(); 
      break; 
     } 
     size++; 
     z = z.parent(); 
    } 

} 

resetHeight от класса AVLnode который я не разрешается изменять, как указано в задании.

public class AVLnode<K,V> implements Position<K,V> { 
private AVLnode<K,V> parent;   // reference to the parent node 
private AVLnode<K,V> left;   // reference to the left child 
private AVLnode<K,V> right;   // reference to the right child 
private DictEntry<K,V> entry;   // reference to the entry stored at the node 
private int height;     // height of the node for checking balance-height property 

public AVLnode(DictEntry<K,V> inputEntry, AVLnode<K,V> inputParent, AVLnode<K,V> inputLeft, AVLnode<K,V> inputRight) 
{ 
    entry = inputEntry; 
    parent = inputParent; 
    left = inputLeft; 
    right = inputRight; 
    height = 0; 
    if (left != null) height = Math.max(height,1+left.getHeight()); 
    if (right != null) height = Math.max(height,1+right.getHeight()); 
} 

public AVLnode<K,V> parent(){ return parent;} 
public AVLnode<K,V> left() {return left;} 
public AVLnode<K,V> right() {return right;} 
public int getHeight() { return height; } 
public DictEntry<K,V> getEntry() { return entry; } 
public void setParent(AVLnode<K,V> newParent){ parent = newParent; } 
public void setLeft(AVLnode<K,V> newLeft) {left = newLeft;} 
public void setRight(AVLnode<K,V> newRight) { right = newRight; } 
public void setEntry(DictEntry<K,V> newEntry) { entry = newEntry; } 
public DictEntry<K,V> element(){return entry;} 

public void resetHeight() throws AVLTreeException{ 
if (left == null || right == null) throw new AVLTreeException("Attempt to update height for external node "); 
height = 1+Math.max(left.getHeight(),right.getHeight()); 
} 

}

Я думаю, что проблема в том, что, когда я использую метод вставки я еще не установлен левый или правый ребенка. Таким образом, getHeight генерирует исключение, поскольку оба дочерних узла узла, которые я вставляю, являются нулевыми. Я не совсем уверен, как это реализовать. Я попытался создать новые узлы для установки как левого и правого дочернего элемента hold, но я не знаю, что я должен указать в качестве параметров, не испортив список, кроме нулевого, но это просто возвращает меня туда, где я был.

Answer 1

Как z не имеет детей, и поэтому не может быть несбалансированным, начинают цикл resetHeight() от родительского z «s:

z.setEntry(temp); 

z = z.parent(); 
while (z != null) { 
     z.resetHeight(); 
     // etc...