Erreur StackOverFlow lors de la conversion de 1 000 000 nœuds dans une arborescence Splay en une SinglyLinkedList

Question

J'ai implémenté une classe Splay Tree qui utilise des nœuds pour stocker des données. Dans cette classe, j'ai essayé de convertir les données des nœuds en une seule liste chaînée. 1.000.000 nœuds peuvent être insérés dans l'arborescence splay et cela fonctionne parfaitement. En utilisant la récursivité, j'obtiens une erreur StackOverFlow lorsque l'arborescence contient 1 000 000 nœuds. Cependant, lorsque l'arbre contient environ 15 000 nœuds, il peut être converti en une liste chaînée sans problème.

Voici le code de ma méthode de toList qui est à l'intérieur de la classe arbre évasement

public LinkedList<Node> toList() { 

    LinkedList<Node> list = new LinkedList<Node>(); 
    Node node = root; 
    addToList(node, list); 

    return list; 
} 

private void addToList(Node node, LinkedList<Node> list) { 
    if(node != null) { 
     addToList(node.left, list); 
     list.add(node); 
     addToList(node.right, list); 
    } 
} 

J'ai utilisé cette classe de test ci-dessous pour tester la fonction de cette méthode

@Test 
public void testConversionToLinkedList { 
    SplayTree<Integer,String> st = new SplayTree<Integer,String>(); 
    for(int i = 0; i < 1000000; i++) { 
     st.insert(i, Integer.toString(i)); 
    } 
    assertEquals(1000000, st.size()); 

    LinkedList<Node> list = st.toList(); 
    assertEquals(1000000, list.size()); 
} 

Le test passe quand la taille entrée est autour de 15000, cependant tout nombre supérieur à celui montrera un StackOverFlowError

L'erreur se produit à la ligne addToList(node.left, list);

C'est vraiment bizarre parce que quand j'ai utilisé la même technique de récurrence pour imprimer les données des noeuds dans un fichier txt, il n'y a pas d'erreur StackOverFlow et les données s'impriment parfaitement.

J'ai essayé d'utiliser In Order Traversal, PreOrder et PostOrder, mais je reçois toujours la même erreur à 1 000 000 nœuds. Je sais que ça pourrait être trop récursif et que la pile manque de mémoire. Si tel est le cas, est-il possible de convertir une arborescence splay de noeuds en une liste chaînée? Une idée de ce qui pourrait mal tourner? acclamations

Answer 1

Votre poblem est l'algorithme récursif. Comme vous l'avez compris, il y a une limite dans la taille de la pile, qui est construite quand vous avez une récursivité.

Vous pouvez toujours transformer la récursivité en boucle.

Voici quelques exemples pour les algorithmes DFS et BFS à l'aide de boucles: Non recursive Depth first search algorithm

Answer 2

Vous pouvez augmenter la taille de la pile. Pour ce faire, vous devez passer le paramètre à jvm. Le format est -Xss [g | G | m | M | k | K]. Par exemple: java -Xss4m YourTreeProgram