AVL Arbre ne supprimera pas tous les nœuds

Question

j'ai donc un test qui supprime un certain nombre d'éléments de la liste (suppression finalement tous):

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");    
} 

Note: Oui, je suis 100% sûr qu'il ya 150 articles dans l'arbre :)

Voici ma méthode de supprimer, supprimer un nœud de l'arbre, puis rééquilibrer l'arbre:

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); 
    } 

Quand je déboguer mon code, le compteur dans le test finit avec un seul, et il y en a un tem à gauche dans la liste. Pour une raison étrange, c'est le 49ème livre dans le dernier et je ne sais pas pourquoi: s

Merci pour l'aide à l'avance!

Answer 1

Parce que je instancier le rootNode être nulle au début, je mise pas vraiment le rootNode lorsque la méthode de suppression est appelée. Par conséquent, il ne faut jamais enlever la racine.

Ainsi, pour corriger l'erreur, j'ajouter:

rootNode = remove(key, value, rootNode); 

Pour la première mise en œuvre de la méthode de suppression! Merci pour la lecture :)