Pourquoi les arbres poussent-ils vers le bas?

17

Pourquoi les arbres poussent-ils vers le bas en informatique?

J'ai l'impression que cela revient à une imprimante et qu'un programme traversant un arbre imprime d'abord la racine et utilise la notion de pile de papier sans fond pour exprimer les niveaux indéfinis de récursivité qui pourraient être rencontrés.

Les références:

Les arbres poussent vers le bas, ayant leurs racines en haut de la page et leurs feuilles en bas

De ON SAINT GUERRES ET UN PLAIDOYER POUR LA PAIX .

par convention, les arbres sont tirés vers le bas

Extrait de l'article Wikipedia sur les structures de données arborescentes.

Les vrais arbres poussent de leur racine vers le ciel, mais les arbres de l'informatique poussent de la racine vers le bas

D'après les notes de cours de David Schmidt .

computer-science conventions maxpolk
la source
8
Pourquoi les regards sont-ils ronds?
Job
9
Arbres cultivés dans toutes les directions dans la nature ... vers le haut, vers le bas, etc.
CaffGeek
7
@Job Pour empêcher les couvercles de trou d'homme de tomber. FTFY. :-)
Gary Rowe
6
@GaryRowe: Un mensonge largement répandu. Les couvercles de trou d'homme sont ronds principalement parce qu'ils recouvrent les extrémités des tuyaux, et les tuyaux sont ronds. Les tuyaux sont ronds car 1) qui répartit uniformément les contraintes sur eux, et 2) ils maximisent la section transversale pour un périmètre donné. Dans l'ensemble, il maximise la résistance et la capacité du tuyau que vous pouvez obtenir à partir d'une quantité spécifique de matériau.
Jerry Coffin
11
@JerryCoffin: Alors .... les arbres poussent vers le bas parce que les tuyaux ronds sont plus solides que les tuyaux carrés? ;)
FrustratedWithFormsDesigner

Réponses:

13

Juste une supposition:

Les structures arborescentes poussent vers le bas (racine en haut, feuilles en bas) parce que les gens lisent du haut de la page vers le bas. De plus, si vous dessiniez un grand arbre s'étalant sur plusieurs pages, il serait gênant de demander au lecteur de sauter quelques pages avant de revenir en arrière.

De plus, que la convention ait commencé pour la raison expliquée ci-dessus ou pour une autre raison, nous continuons la pratique aujourd'hui exactement parce que c'est une convention. Nous avons des termes correspondants comme nœud de niveau supérieur (signifiant la racine) qui n'auraient pas autant de sens si nous dessinions la structure avec la racine en bas.

Caleb
la source
1
@BruceEdiger: Je vais deviner que cela se résume à différentes conventions.
FrustratedWithFormsDesigner
3
@BruceEdiger C'est quelque chose de très différent. Le système de coordonnées cartésiennes a été établi il y a 375 ans, il est donc assez naturel de s'en tenir à cette convention. Les systèmes graphiques (X11, QuickDraw, Quartz sur iOS) utilisent souvent un système de coordonnées inversé. Je ne pense pas que cela ait quoi que ce soit à voir avec la façon dont nous dessinons les arbres.
Caleb
3
À mon humble avis, la raison des coordonnées inversées remonte à l'époque où l'on avait des terminaux. Puisqu'ils affichaient du texte commençant dans le coin supérieur gauche et que la résolution réelle pouvait varier, il était très raisonnable de prendre (0,0) comme coin supérieur gauche.
FUZxxl
1
Les coordonnées à l'écran @BruceEdiger correspondent essentiellement de (x, y) à l'emplacement de mémoire du pixel / caractère. Les contrôleurs d'affichage vidéo chargés de mapper la mémoire à une image commencent à l'emplacement 0 dans le coin supérieur gauche. Par conséquent, c'est un mappage naturel d'avoir (0,0) là-bas car vous pouvez obtenir l'emplacement de mémoire juste avec (y * 80 + x). Documentation pour l'ordinateur 8 bits J'ai appris cela avec: datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf
2
Lorsque vous dessinez un arbre à la main, il est difficile de savoir de combien d'espace vous aurez besoin, il est également difficile de disposer soigneusement les notes sans d'abord dessiner le niveau ci-dessus. Vous avez donc tendance à dessiner la «racine» en la plaçant en haut pour pouvoir continuer avec votre texte où que ce soit sur la page où se termine l'arborescence.
Ian
16

La convention semble découler de l' algorithme Coffman-Graham qui est conçu:

"... pour organiser les éléments d'un ensemble partiellement ordonné en une séquence de niveaux. L'algorithme choisit une disposition telle qu'un élément qui vient après un autre dans l'ordre est affecté à un niveau inférieur et que chaque niveau ait un numéro d'éléments qui ne dépasse pas une largeur fixe liée W. "

Leur article de 1972 ( PDF ) montre un graphique acyclique dirigé dessiné de haut en bas. Il s'agit d'une étape courte pour représenter un arbre de la même manière.

Il y a quelques commentaires supplémentaires sur cette visualisation dans cet article sur le dessin de graphiques en couches .

Gary Rowe
la source
1
The Art of Computer Programming: Fundamental Algorithms, Volume 1 - Fundamental Algorithms, a été publié en 1968 et comportait une section 2 sur les arbres. Quelqu'un qui possède ce livre peut-il vérifier que les diagrammes montrent des arbres qui poussent? Si c'est le cas, l'histoire nous indique une convention commencée encore plus tôt. De plus, je me demande si l'informatique a repris des mathématiques cette convention même avant 1960. Wolfram montre que les arbres ont été étudiés en 1857.
maxpolk
3
@maxpolk Knuth dessine ses arbres de la racine en haut et discute de sa décision (sec. 2.3, pp. 311 dans la 3e édition) de convertir la forme racine en bas avant la publication de la première édition. Cela se résume à «la plupart de la littérature existante va de haut en bas, et nous avons besoin d'un modèle cohérent à des fins de discussion» (80% selon l'enquête de Knuth).
Ross Patterson
1

Les dessins de top > downet left > rightsont populaires en informatique car ce sont les directions de départ en anglais écrit. Étant donné que la plupart des articles sur l'informatique sont rédigés en anglais, quelle que soit la langue maternelle de l'auteur, ce serait la façon la plus courante de dessiner des diagrammes.

Il est très naturel pour un lecteur de langue anglaise de lire un graphique à partir de top > downou left > rightde l'une des autres alternatives.

Effectuez une recherche sur images.google.com directed tree graphet examinez les résultats. Les seuls diagrammes d'arbre que j'ai pu trouver qui ont été montés étaient les diagrammes de classes UML, et uniquement parce que c'est la convention que UML a choisie pour les diagrammes de classes. Tous les autres diagrammes UML vont left > rightou up > down.

Je considérerais la lecture de graphiques d'arbre dirigés down > upaussi peu naturelle que la lecture des fils de discussion les plus populaires; ce qui est complètement anti-naturel.


la source