Arbre Splay récursif

Question

J'essaye d'implémenter une arborescence récursive, de bas en haut. Je reviens au nœud que j'ai besoin de visualiser, et je trouve le parent et le grand-parent de ce nœud. Ensuite, je suis en mesure de zig zag ou zig zig en fonction de la situation très bien. Le problème est après que ceci est fait, je retourne le noeud qui a été évidé une fois à l'appel récursif précédent. L'appel récursif précédent est référencé au parent du nœud, qui est maintenant l'enfant de ce nœud. Comment est-ce que je me rouvre en écartant le nœud au fur et à mesure que je monte?

Answer 1

Si je me souviens bien, vous construisez un arbre gauche et droit lorsque vous vous recourez vers le noeud cible. Lorsque vous trouvez la cible, vous construisez les arbres finaux gauche et droit en utilisant les enfants (originaux) de la cible, attachez les arbres résultants en tant que nouveaux enfants de la cible, et renvoyez le résultat de manière récursive (c.-à-d. remonter la pile sans autre modification).

Answer 2

Lorsque l'arborescence est totalement "déséquilibrée" et très grande (disons par exemple 100000 int), les algorithmes récursifs peuvent déclencher une exception stackoverflow. Mieux vaut utiliser un pointeur parent dans chaque nœud pour obtenir le parent ou le grand parent. C'est une façon de le faire. a bien fonctionné pour moi.

Les résultats sur le moteur d'exécution sont évidents ici splay tree runtime profiling