Trier un arbre non ordonné par la quantité de nœuds-enfants qu'un nœud a

Question

Je travaille actuellement sur "Algorithms in java" de Robert Sedgewick (3ème édition, version allemande) et j'essaie de résoudre l'un des exercices là, actuellement un de la section "creative-solutions".

Dans le cadre de la solution d'un exercice que je suis en train de trier un arbre par la quantité non triés des enfants chaque noeud a, noeuds avec des quantités plus grandes d'enfants venant en premier:

1. Trier tous les nœuds enfants d'un parent n0 selon la quantité de nœuds enfants nNodes que possèdent les nœuds enfants eux-mêmes, trier de gauche à droite du plus grand au plus bas. Effectuez ce tri pour tous les nœuds de l'arborescence.
2. Si 2 noeuds-frères n1 et n2 de ces noeuds-enfants ont nNodes identiques, allez aux noeuds-enfants de n1 et n2 essayez de trier ces deux-là en fonction du nNodes de leurs plus grands enfants. Si aucune différence n'est trouvée, essayez de trier en fonction du nNodes de leurs 2e plus grands enfants, etc.
3. Si vous n'avez plus d'enfants, rendez-vous au nœud d'enfant de l'enfant dans 2 avec le plus grand nombre d'enfants et répétez 2. etc. etc.
4. Si, après toutes les comparaisons, il s'avère que n1 et n2 sont tous deux des racines d'arbres de forme identique, peu importe lequel des deux vient en premier.

Pour donner une comparaison visuelle, cette « règle » entraînerait le tri des arbres suivant comme décrit ici: Example of Sorting.

Le code

Le problème que je suis bloqué à la mise en œuvre est correctement le tri. Chaque arbre est composé de nœuds. Chaque nœud contient une valeur (de sorte que vous avez un "nom" pour le nœud, pas important pour le tri lui-même qui ne se soucie que du nombre d'enfants de chaque nœud) et une liste de références de nœuds aux nœuds enfants de ce nœud nœud. Pour les nœuds sans enfants, ArrayList a la taille 0. La clé consiste ici à trier les ArrayLists dans tous les nœuds, ce que j'essaie actuellement de faire en utilisant la méthode de tri intégrée avec un objet Comparator. Je pense que je dois aborder cela de façon récursive, ce qui rend le tout vraiment désordonné parce que j'ai actuellement une méthode de comparaison qui s'appelle tout en appelant "sort" pour d'autres ArraLists dans la même méthode. La méthode sortForest ci-dessous me donne des erreurs de débordement de pile lorsque je l'essaye dans certaines méthodes principales pour le tester.

static NodeComparator comp = new NodeComparator(); 

    static class Node { 
     int value; 
     ArrayList<Node> children; 

     Node(int value, ArrayList<Node> children) { 
      this.value = value; 
      this.children = children; 
     } 
    } 

    static class NodeComparator implements Comparator<Node> { 
     public NodeComparator() { 
     } 

     public int compare(Node n1, Node n2) { 
      /*- 
      * Base Case 1: Both Nodes are leafs (isEmpty() is true) - they are 
      * equal -> return 0. 
      * Base Case 2/3: One of the Nodes is a leaf while the other isn't - 
      * the one that is a leaf is "lower" than the one that isn't. -> 
      * return (-) 1. 
      */ 
      if (n1.children.isEmpty() && n2.children.isEmpty()) { 
       return 0; 
      } else if (n2.children.isEmpty()) { 
       n1.children.sort(comp); 
       return 1; 
      } else if (n1.children.isEmpty()) { 
       n2.children.sort(comp); 
       return -1; 
      } else { 
       /* Get the amount of children the 2 nodes n1 and n2 have */ 
       int nChildren1 = (n1.children.isEmpty()) ? 0 : n1.children.size(); 
       int nChildren2 = (n2.children.isEmpty()) ? 0 : n2.children.size(); 
       /* Always sort the ArrayList of children that they have */ 
       n1.children.sort(comp); 
       n2.children.sort(comp); 

       /* 
       * If n1 and n2 have equal amounts of children, compare the 
       * amounts of children their children have, from largest to 
       * lowest 
       */ 
       if (nChildren1 == nChildren2) { 
        int result = 0; 
        for (int i = 0; (i < nChildren1) && (result == 0); i++) { 
         compare(n1.children.get(i), n2.children.get(i)); 
        } 
        return result; 
       } else { 
        /*- If one node has more children than the other, sort accordingly */ 
        return ((nChildren1 > nChildren2) ? 1 : -1); 
       } 
      } 
     } 
    } 

    static void sortForest(Node root) { 
     for (int i = 0; i < root.children.size(); i++) { 
      sortForest(root.children.get(i)); 
      root.children.sort(comp); 
     } 
     return; 
    } 

Question

Comment peut-on obtenir ce code au travail? Je suis un peu sûr que c'est à peu près dans le cadre d'une solution correcte, mais j'ai essayé de réfléchir à cela pendant plusieurs heures maintenant et je n'arrive pas à en trouver un. Je suis convaincu que cela me donne des débordements de pile en raison d'une récursion sans fin qui se trouve quelque part, je ne le vois tout simplement pas. La récursivité en général me donne des problèmes pour le faire correctement mentalement. Je ne pouvais pas trouver des questions identiques à ceci et ceux qui étaient semblables se sont occupés des arbres binaires au lieu des unsordered.

Answer 1

Il y a plusieurs choses mal avec le code ci-dessus:

1. Le code suppose que le noeud racine de chaque arbre ne contenait pas de référence à lui-même (non représenté dans le code ci-dessus), qui à l'origine a causé la méthode de comparaison pour appeler la racine encore et encore, cela a été rectifié.

2. Il est absolument inutile et incorrect d'appeler le tri dans la méthode de comparaison. Le code appelle déjà des méthodes de tri pour chaque nœud avec sortForest(), à partir des feuilles, donc cela n'a pas sa place et doit être retiré de toutes les parties du code de la méthode de comparaison.

3. Avec le retour donné, la méthode compare n'aboutit pas à un tri du plus grand au plus petit, mais du plus petit au plus grand. Il doit retourner 1 où il renvoie -1 et vice versa. La méthode de comparaison nécessite également, dans sa boucle for, de stocker le retour de compare() dans result, sinon le résultat ne change jamais et la boucle ne s'arrête pas une fois qu'une discordance a été trouvée.

4. Le tri avec root.children.sort(comp); dans sortForest() absolument doit se produire en dehors du ForLoop, sinon vous triez une partie de la ArrayList pendant que vous avez encore besoin dans leur ordre d'origine pour effectuer tous les appels correctement.

Après rectification de tous ceux-ci, les sortForest() et compare() méthodes ci-dessus ont livré les résultats de tri correct par exemple des arbres comme:

int[] tree1 = { 2, 3, 3, 3, 2, 2, 1, 0, 7, 5, 3, 10, 10, 6 };

int[] tree2 = { 4, 10, 11, 0, 4, 0, 12, 4, 7, 8, 0, 3, 4, 12 };

Et les trier comme indiqué dans this picture .

Le code complet de la solution ainsi que quelques optimisations et la suppression du code inutile et avec le tri fixe se trouvent here

Answer 2

En fonction de la taille de l'arborescence, vous risquez d'être confronté à des limitations lors de l'appel au sortForest concernant la taille de la pile par défaut de Java. Les moyens de le contourner comprennent de l'augmenter via l'option JVM -Xss, en définissant la taille de la pile dans le Threadconstructor, en le réécrivant de manière non-récursive ou en utilisant le Trampoline pattern.