AVL дерева не будут удалены все узлы

Question

Так я тест, который удаляет ряд элементов из списка (в конечном счете, удаляя все из них):

for (int i=1; i<=150;i++) { 
    String id = "T" + i; 
    Iterator<Item> iter6 = tree.find(id); 
    if (iter6.hasNext()) { 
     Item item = iter6.next(); 
     tree.remove(id, item); 
    } 
} 
Iterator<Item> all6 = tree.listAll(); 
int counter6 = 0; 
while(all6.hasNext()) { 
    counter6++; 
    all6.next(); 
} 
if (counter6==0) { 
    System.out.println("TEST 6 pass"); 
} else { 
    System.out.println("TEST 6 fail");    
} 

Примечание: Да, я 100% уверен, что есть 150 элементов внутри дерева :)

Вот мой метод удалить, удалить узел из дерева, а затем восстановить баланс дерева:

public class AVLTree<K, V> implements IAVLTree<K, V> 
{ 
    public class Node { 
     private K key; 
     private ArrayList<V> valuesList; 
     private Node left, right; 
     private int height; 

     public Node(K key, ArrayList<V> valuesList) { 
      this.key = key; 
      this.valuesList = valuesList; 
      this.height = 0; 
     } 

     public Node(V value) { 
     } 

     public void addToNode(V value) { 
      valuesList.add(value); 
     } 

     public K getKey() { 
      return key; 
     } 

     public ArrayList<V> getValues() { 
      return valuesList; 
     } 

     public Node getChildNodeFromSide(String side) { 
      switch(side) { 
       default: return null; 
       case "left": return left; 
       case "right": return right; 
      } 
     } 
    } 

    private Node rootNode; 
    private Comparator<K> comparator; 

    //Unused 
    public AVLTree() { 
    } 

    public AVLTree(Comparator<K> comparator) { 
     this.comparator = comparator; 
     this.rootNode = null; 
    } 

    @Override 
    public V remove(K key, V value) throws Exception { 
     remove(key, value, rootNode); 
     return value; 
    } 
    private Node remove(K key, V value, Node node) { 
     //If node with key contains one or less values, remove the whole key 
     //Else remove value from node with key 
     if(node == null) return null; 
     else if(comparator.compare(key, node.key) < 0) { 
      node.left = remove(key, value, node.left); 

      if(height(node.left) - height(node.right) == 2) { 
       if(comparator.compare(key, node.left.key) < 0) 
        node = rotateWithLeftChild(node); 
       else 
        node = doubleRotateWithLeft(node); 
      } 
     } else if(comparator.compare(key, node.key) > 0) { 
      node.right = remove(key, value, node.right); 

      if(height(node.right) - height(node.left) == 2) { 
       if(comparator.compare(key, node.right.key) < 0) 
        node = rotateWithRightChild(node); 
       else 
        node = doubleRotateWithRight(node); 
      } 
     } else { 
      if(node.valuesList.size() > 1) { 
       node.valuesList.remove(value); 
       return node; 
      } else { 
       if(node.left == null && node.right == null) 
        return null; 
       if(node.left == null) return balance(node.right); 
       if(node.right == null) return balance(node.left); 

       Node smallestNode = smallestNode(node.right); 
       node = smallestNode; 
       node.right = remove(key, value, node.right); 
       return balance(node); 
      } 
     } 

     return balance(node); 
    } 

    private Node rotateWithLeftChild(Node node2) { 
     Node node1 = node2.left; 
     node2.left = node1.right; 
     node1.right = node2; 

     node2.height = Math.max(height(node2.left), height(node2.right)) + 1; 
     node1.height = Math.max(height(node1.left), node2.height) + 1; 

     return node1; 
    } 
    private Node rotateWithRightChild(Node node1) { 
     Node node2 = node1.right; 
     node1.right = node2.left; 
     node2.left = node1; 

     node1.height = Math.max(height(node1.left), height(node1.right)) + 1; 
     node2.height = Math.max(height(node2.left), node1.height) + 1; 

     return node2; 
    } 
    private Node doubleRotateWithLeft(Node node) { 
     node.left = rotateWithRightChild(node.left); 
     return rotateWithLeftChild(node); 
    } 
    private Node doubleRotateWithRight(Node node) { 
     node.right = rotateWithLeftChild(node.right); 
     return rotateWithRightChild(node); 
    } 

    private Node balance(Node node) { 
     node.height = Math.max(height(node.left), height(node.right)) + 1; 
     return node; 
    } 
    private Node smallestNode(Node node) { 
     if(node.left == null) return node; 
     else return smallestNode(node.left); 
    } 

Когда я отладки мой код, счетчик в тесте заканчивается с одним, и есть один i в списке осталось. По какой-то нечетной причине это 49-я книга в последнем, и я понятия не имею, почему: s

Спасибо за помощь заранее!

Answer 1

Потому что я экземплярRootNode быть нулевой в самом начале, я на самом деле не устанавливая RootNode когда метод удалить называется. Поэтому он никогда не удаляет корень.

Таким образом, чтобы исправить ошибку, я добавляю:

rootNode = remove(key, value, rootNode); 

К первой реализации способа удалить!

Спасибо в любом случае за чтение :)