Un arbre peut-il être parcouru sans récursivité, pile ou file d'attente, et juste une poignée de pointeurs?

15

Il y a une demi-décennie, j'étais assis dans une classe de structures de données où le professeur offrait un crédit supplémentaire si quelqu'un pouvait traverser un arbre sans utiliser la récursivité, une pile, une file d'attente, etc. (ou toute autre structure de données similaire) et seulement quelques pointeurs. J'ai trouvé ce que je pensais être une réponse évidente à cette question qui a finalement été acceptée par le professeur. J'étais assis dans un cours de mathématiques discret avec un autre professeur du même département - et il a affirmé qu'il était impossible de traverser un arbre sans récursivité, pile, file d'attente, etc., et que ma solution n'était pas valide.

Alors, est-ce possible ou impossible? Pourquoi ou pourquoi pas?

Edit: Pour ajouter des éclaircissements, j'ai implémenté cela sur un arbre binaire qui avait trois éléments - les données stockées à chaque nœud et les pointeurs vers deux enfants. Ma solution pourrait être étendue aux arbres n-aires avec seulement quelques changements.

Mon professeur de structures de données n'a mis aucune contrainte contre la mutation de l'arbre, et j'ai en effet découvert plus tard que sa propre solution était d'utiliser les pointeurs enfants pour remonter l'arbre en descendant. Mon professeur de mathématiques discret a déclaré que toute mutation d'un arbre signifie que ce n'est plus un arbre selon la définition mathématique d'un arbre, sa définition exclurait également tous les pointeurs vers les parents - ce qui correspondrait au cas où je l'ai résolu ci-dessus.

NL - Excusez-vous auprès de Monica
la source
3
Vous devez spécifier les contraintes. Suis-je autorisé à muter l'arbre? Comment l'arbre est-il représenté? (Par exemple, chaque nœud a-t-il un pointeur parent vers son parent?) La réponse dépendra des contraintes spécifiques; sans préciser ces contraintes, ce n'est pas un problème bien posé.
DW
2
Je suppose que la contraint que les professeurs voulaient vraiment exprimer était "avec espace supplémentaire". Mais quelle était votre solution, de toute façon? O(1)
Raphael

Réponses:

17

De nombreuses recherches dans ce domaine ont été menées sur le dôme, motivées par une méthode de traversée «bon marché» des arbres et des structures de listes générales dans le contexte de la collecte des ordures.

Un arbre binaire fileté est une représentation adaptée d'arbres binaires où certains pointeurs nuls sont utilisés pour se lier aux nœuds successeurs de l'arbre. Ces informations supplémentaires peuvent être utilisées pour parcourir un arbre sans pile. Cependant, un bit supplémentaire par nœud est nécessaire pour distinguer les threads des pointeurs enfants. Wikipédia: Tree_traversal

Autant que je sache, les arbres binaires implémentés à l'aide de pointeurs de la manière habituelle (pointeurs gauche et droit par nœud) peuvent être parcourus en utilisant la méthode des threads, dans une méthode attribuée à Morris . Les pointeurs NIL sont temporairement réutilisés pour renvoyer un chemin à la racine. La partie intelligente est que pendant la traversée, on peut distinguer les bords d'origine des liens de fil temporaires, en utilisant la façon dont ils forment des cycles dans l'arbre).

Bonne partie: pas de structure de données supplémentaire. Mauvaise partie: triche légèrement, la pile est à l' intérieur de l'arbre de manière intelligente. Très intelligent.

Une preuve de la pile cachée est présentée dans P. Mateti et R. Manghirmalani: Morris's Tree Traversal Algorithm Reconsidered DOI: 10.1016 / 0167-6423 (88) 90063-9

JM Morris: Traverser des arbres binaires simplement et à moindre coût. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

Ensuite, il y a aussi la numérisation Lindstrom . Cette méthode "fait tourner" les trois pointeurs impliqués dans chaque nœud (parent et deux enfants). Si vous souhaitez exécuter des algorithmes décents de pré-commande ou de post-commande, vous avez besoin de bits supplémentaires par nœud. Si vous souhaitez simplement visiter tous les nœuds (trois fois, mais vous ne savez jamais quelle visite vous effectuez), cela peut être fait sans les bits.

G. Lindstrom: Analyse des structures de liste sans piles ni bits d'étiquette. IPL 2 (1973) 47-51. EST CE QUE JE: 10.1016 / 0020-0190 (73) 90012-4

Le moyen le plus simple est peut-être une méthode Robson . Ici, la pile nécessaire pour l'algorithme classique est enfilée à travers les feuilles.

JM Robson: Un algorithme amélioré pour parcourir les arbres binaires sans pile auxiliaire IPL 1 (1973) 149-152. 10.1016 / 0020-0190 (73) 90018-5

IPL = Lettres de traitement de l'information

Hendrik Jan
la source
J'aime aussi cette solution, mais ce n'est rien que j'aurais imaginé pendant ma première année de cours d'informatique. Ouais, triche probablement selon les règles de mon professeur.
NL - Présentez vos excuses à Monica
2
Pouvez-vous donner des liens / références pour les stratégies?
Raphael
1
La vraie mauvaise partie de cette méthode est que vous ne pouvez pas avoir plus d'une traversée en cours à la fois.
Gilles 'SO- arrête d'être méchant'
6

v

Yuval Filmus
la source
Ceci est similaire à la solution que le professeur de structures de données qui a proposé le problème a utilisée pour le résoudre. Le professeur de mathématiques discret a objecté que "cela est devenu un graphique plutôt qu'un arbre" s'il y a des pointeurs vers les parents.
NL -
@NathanLiddle: Cela dépend de la définition d'arbre utilisée (que vous n'avez pas donnée). Dans le «monde réel», la représentation en arbre de Yuval est raisonnable même si la théorie des graphes dirait que les choses qu'il définit ne sont pas des arbres, bien sûr.
Raphael
@Raphael Oui, et il répond aux exigences du professeur d'origine, c'est donc une réponse acceptable pour moi.
NL - Présentez vos excuses à Monica
0

Ma solution était une traversée avant-gardiste utilisant des boucles for imbriquées pour forcer brutalement l'arbre. Ce n'est en aucun cas efficace, et en effet une structure de données récursive comme un arbre demande une traversée récursive, mais la question n'était pas de savoir si un arbre pouvait être traversé efficacement, était de savoir si c'était même possible.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Pour les premiers niveaux, cela ressemblerait à cela, comme vous pouvez le voir, l'opérateur au niveau du bit dans le pseudocode décide simplement d'un virage à gauche ou à droite sur un arbre binaire:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

Pour n-aire, vous devez prendre i% (maxChildren ** j) / j pour déterminer le chemin à prendre entre 0 et maxChildren.

À chaque nœud sur n-aire, vous devrez également vérifier si le nombre d'enfants est supérieur à maxChildren et le mettre à jour de manière appropriée.

NL - Excusez-vous auprès de Monica
la source
Si vous vouliez utiliser plus que binaire, vous auriez besoin de remplacer le nombre magique 2 par une variable qui serait incrémentée pour correspondre au nombre maximal d'enfants qu'il a vu, et au lieu d'opérateurs au niveau du bit, vous devrez diviser par la même variable élevée à la puissance de la profondeur de l'arbre où vous étiez.
NL - Présentez vos excuses à Monica
O(1)O(lgn)O(1)O(n)O(1)depthint
DW, le professeur qui a posé le problème n'a pas mis cette contrainte sur le problème, et ce qui m'a tellement dérangé dans ma discussion avec le professeur de mathématiques discret, c'est qu'il n'a JAMAIS reconnu qu'il était même possible de traverser un arbre sans récursivité, pile, ou faire la queue, quel qu'en soit le prix. La seule chose que ma solution démontre est qu'il est possible de faire de manière itérative ce qui peut être fait de manière récursive, même si vous supprimez des options pour la pile, la file d'attente, etc.
NL - Excusez-vous auprès de Monica
C'est une chose de dire qu'il est insoluble sans O (1) d'espace supplémentaire, c'est une tout autre chose de déclarer le problème insoluble sans récursivité, pile ou file d'attente. Et en fait, après avoir vu mon code, le professeur de mathématiques discret ne voulait toujours pas concéder le point parce qu'il avait dit que "i" dans la première boucle for remplaçait une file d'attente. Comment est-ce pour les têtes dures?
NL - Excusez-vous auprès de Monica
1
idepthdepthΘ(n)Θ(n)iO(1)