Dépassement de pile lors de la tentative d'implémentation d'une rotation pour AVL Tree

Question

Chaque fois que j'ajoute un nouveau noeud dans l'arborescence, il le trie d'abord comme un arbre binaire puis recherche récursivement les violations dans AVL. Le problème est dans ma fonction de rotation J'ai essayé de tester la violation AVL qui nécessite une rotation gauche-gauche et quand je fais cela en créant d'abord une racine, puis en créant un enfant droit a puis un autre enfant gauche b de une. Maintenant, ce qui se passe est qu'elle émette a jusqu'à la fin puis je reçois une erreur disant:

Exception in thread "main" java.lang.StackOverflowError

at AVLTree$AVLNode.height(AVLTree.java:63)

at AVLTree$AVLNode.height(AVLTree.java:62)

Je ne sais vraiment pas comprendre le problème

54 int getBalance(){ 
55  int leftHeight = (left == null)?0:left.height(); 
56  int rightHeight = (right == null)?0:right.height(); 
57  
58  return leftHeight - rightHeight; 
59 } 
61 int height(){ 
62  int leftHeight = (left == null)?0:left.height(); 
63  int rightHeight = (right == null)?0:right.height(); 

     return 1 + Math.max(leftHeight, rightHeight); 
    }  

public void rotate(AVLNode test){ 
     System.out.println(test.getBalance()); 
     if(Math.abs(test.getBalance()) < 2){ 

      if(test.getParent() != null){ 
       rotate(test.getParent()); 
      } 
      else{ 
       return; 
      } 
     } 
     if(test.getBalance() <= -2){ 

      System.out.println(test.getBalance()); 

      if(test.getRight().getBalance() <= 0){ 

       System.out.println("i'm in"); 
       AVLNode parent = test.getParent(); 

       if(parent != null){ 

        if(parent.getLeft() == test){ 
         parent.setLeft(test.getRight()); 
        } 
        else{ 
         parent.setRight(test.getRight()); 
        } 
       } 

       else{ 
        this.root = test.getRight(); 
       } 
       test.setParent(test.getRight()); 

       if(test.getRight().getLeft() != null){ 

       test.getRight().getLeft().setParent(test); 
       test.setRight(test.getRight().getLeft()); 
       } 

       test.getParent().setLeft(test); 
       System.out.println("got till the end"); 
      } 
     } 

Answer 1

int height(){ 
     int leftHeight = (left == null)?0:left.height(); 
     int rightHeight = (right == null)?0:right.height(); 
     return 1 + Math.max(leftHeight, rightHeight); 
    } 

---

ce recursive method n'a pas exit quand left n'est pas null il invoquera left.height() left.height() left.height() left.height() .... .... jusqu'à épuisement de la pile

Answer 2

Je pense que vous avez un problème avec la méthode rotate, bien qu'il soit difficile de déboguer juste en lisant le code. Il me semble que vous obtenez une référence cyclique qui provoque alors StackOverflow dans la méthode height. Bien que height soit l'endroit où le débordement se produit selon la trace de la pile, cela ne devrait pas se produire à moins qu'il n'y ait des cycles dans la structure arborescente. Si l'un des noeuds a lui-même un enfant gauche, par exemple, cela arrivera.

Je ne suis pas vraiment au courant de l'algorithme AVL, mais il me semble comme une source d'erreur (peut-être pas le seul) dans votre méthode rotate est que parent « enfant gauche s pourrait se mettre à test » s enfant droit, mais le parent de l'enfant droit du test n'est jamais défini sur parent.

Encore une fois, il est assez difficile de lire et de déboguer le code comme ceci. Une suggestion est d'essayer de diviser l'algorithme en plus petits morceaux, ou de faire de petites fonctions d'aide faciles à vérifier.

Answer 3

Mon idée est que si nous devons calculer la hauteur de noeud calcule alors la hauteur de son enfant enfant et à droite à gauche puis
return 1 + Math.max(leftHeight, rightHeight)
le code complet peut être ceci:

int height(TreeNode tn){ 
     if(tn==null){return 0;} 
     int leftHeight = tn.left.height(); 
     int rightHeight = tn.right.height(); 
     return 1 + Math.max(leftHeight, rightHeight); 
    }