¿Por qué los árboles crecen hacia abajo?

17

¿Por qué los árboles crecen hacia abajo en informática?

Tengo la sensación de que se remonta a una impresora, y que un programa que atraviesa un árbol primero imprime la raíz, y utiliza la noción de una pila de papel sin fondo para expresar los niveles indefinidos de recursión que se pueden encontrar.

Referencias

Los árboles crecen hacia abajo, tienen sus raíces en la parte superior de la página y sus hojas debajo

De ON SANTAS GUERRAS Y UNA SOLICITUD DE PAZ .

por convención, los árboles se dibujan creciendo hacia abajo

Del artículo de Wikipedia sobre estructuras de datos de árbol.

Los árboles reales crecen desde su raíz hacia el cielo, pero los árboles de informática crecen desde la raíz hacia abajo

De las notas de conferencia de David Schmidt .

computer-science conventions maxpolk
fuente
8
¿Por qué son redondas las alcantarillas?
Trabajo
9
Árboles que crecen en todas las direcciones de la naturaleza ... hacia arriba, hacia abajo, etc.
CaffGeek
77
@ Job Para evitar que caigan las tapas de alcantarilla. FTFY. :-)
Gary Rowe
66
@GaryRowe: una falsedad ampliamente propagada. Las tapas de registro son redondas principalmente porque cubren los extremos de las tuberías, y las tuberías son redondas. Las tuberías son redondas porque 1) distribuye la tensión de manera uniforme y 2) maximiza la sección transversal para un perímetro dado. En general, maximiza la resistencia y la capacidad de la tubería que puede obtener de una cantidad específica de material.
Jerry Coffin
11
@JerryCoffin: Entonces ... ¿los árboles crecen hacia abajo porque las tuberías redondas son más fuertes que las cuadradas? ;)
FrustratedWithFormsDesigner

Respuestas:

13

Solo una suposición:

Las estructuras de los árboles crecen hacia abajo (raíz en la parte superior, hojas en la parte inferior) porque las personas leen desde la parte superior de la página hacia la parte inferior. Además, si dibujara un árbol grande que abarcara varias páginas, sería incómodo pedirle al lector que salte algunas páginas y luego retroceda.

Además, si la convención comenzó por la razón explicada anteriormente o por alguna otra razón, continuamos la práctica hoy exactamente porque es una convención. Tenemos términos correspondientes como nodo de nivel superior (que significa la raíz) que no tendría tanto sentido si dibujáramos la estructura con la raíz en la parte inferior.

Caleb
fuente
1
@BruceEdiger: Voy a adivinar que todo se reduce a diferentes convenciones.
FrustratedWithFormsDesigner
3
@BruceEdiger Eso es algo muy diferente. El sistema de coordenadas cartesianas se estableció hace 375 años, por lo que es bastante natural cumplir con esa convención. Los sistemas gráficos (X11, QuickDraw, Quartz en iOS) a menudo usan un sistema de coordenadas invertido. Sin embargo, no creo que tenga nada que ver con la forma en que dibujamos árboles.
Caleb
3
En mi humilde opinión, la razón de las coordenadas invertidas se remonta a la época en que uno tenía terminales. Dado que mostraban texto comenzando desde la esquina superior izquierda y la resolución real puede variar, fue una decisión muy razonable hacer que (0,0) sea la esquina superior izquierda.
FUZxxl
1
Las coordenadas en pantalla de @BruceEdiger se asignan esencialmente desde (x, y) a la ubicación de memoria del píxel / personaje. Los controladores de visualización de video responsables de asignar la memoria a una imagen comienzan en la ubicación 0 en la esquina superior izquierda. Por lo tanto, es un mapeo natural tener (0,0) allí, ya que puede obtener la ubicación de la memoria solo con (y * 80 + x). Documentación para la computadora de 8 bits con la que aprendí esto: datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf
2
Al dibujar un árbol a mano, es difícil saber cuánto espacio necesitará, también es difícil diseñar las notas de forma ordenada sin dibujar primero el nivel superior. Por lo tanto, tiende a dibujar la "raíz" primero poniéndola en la parte superior para que pueda continuar con su texto en cualquier lugar de la página en que finalice el árbol.
Ian
16

La convención parece provenir del algoritmo de Coffman-Graham que está diseñado:

"... para organizar los elementos de un conjunto parcialmente ordenado en una secuencia de niveles. El algoritmo elige una disposición tal que un elemento que viene después de otro en el orden se asigne a un nivel inferior, y que cada nivel tenga un número de elementos que no excede un ancho fijo limitado W. "

Su artículo de 1972 ( PDF ) muestra un gráfico acíclico dirigido que se dibuja de arriba a abajo. Es un paso corto representar un árbol de la misma manera.

Hay algunos comentarios adicionales sobre esta visualización en este artículo sobre Dibujo de gráfico en capas .

Gary Rowe
fuente
1
El arte de la programación de computadoras: Algoritmos fundamentales, Volumen 1 - Algoritmos fundamentales, se publicó en 1968 y tenía una sección 2 sobre árboles. ¿Puede alguien que posee este libro verificar que los diagramas muestren árboles que crecen? Si es así, la historia nos señala una convención que comenzó incluso antes. Además, me pregunto si la ciencia de la computación aprendió de las matemáticas de esta convención incluso antes de 1960. Wolfram muestra que los árboles fueron estudiados en 1857.
maxpolk
3
@maxpolk Knuth dibuja sus árboles desde la raíz hacia arriba y discute su decisión (sec. 2.3, pp. 311 en la 3ra edición) de convertir la forma de raíz en la parte inferior antes de la publicación de la primera edición. Se reduce a "la mayor parte de la literatura existente va de arriba abajo, y necesitamos un modelo consistente para propósitos de discusión" (80% según la encuesta de Knuth).
Ross Patterson
1

Se basa en top > downy left > rightson populares en informática porque esas son las instrucciones iniciales en inglés escrito. Teniendo en cuenta que la mayoría de los artículos de informática están escritos en inglés, independientemente del idioma nativo del escritor, esta sería la forma más frecuente de dibujar diagramas.

Es más natural para un lector de idioma Inglés para leer un gráfico a partir de top > downo left > rightque cualquiera de las otras alternativas.

Realice una búsqueda en images.google.com directed tree graphy revise los resultados. Los únicos diagramas de árbol que pude encontrar que iban arriba eran diagramas de clases UML, y sólo porque esa es la convención que eligió para UML diagramas de clases. Todos los demás diagramas UML van left > righto up > down.

Consideraría leer gráficos de árbol dirigidos de down > uptan poco naturales como leer los hilos de correo electrónico más publicados; lo cual es completamente natural.


fuente