Dlaczego drzewa rosną w dół?

Dlaczego w informatyce rosną drzewa?

Mam wrażenie, że wraca do drukarki i że program przemierzający drzewo najpierw drukuje korzeń i używa pojęcia bezdennego stosu papieru, aby wyrazić nieokreślony poziom rekurencji, który można napotkać.

Bibliografia:

Drzewa rosną w dół, a ich korzenie znajdują się u góry strony, a liście poniżej

Z ON WOJNY ŚWIĘTE I PLEA O POKOJ .

zgodnie z konwencją drzewa rosną w dół

Z artykułu w Wikipedii na temat struktur danych drzewa.

Prawdziwe drzewa rosną od korzenia w górę do nieba, ale drzewa informatyczne rosną od korzenia w dół

Z notatek z wykładu Davida Schmidta .

computer-science conventions maxpolk
źródło

Dlaczego włazy są okrągłe?

Job

Drzewa rosnące we wszystkich kierunkach w naturze ... w górę, w dół itp.

CaffGeek

@ Zadanie Aby zapobiec wpadnięciu pokryw włazu. FTFY. :-)

Gary Rowe

@GaryRowe: szeroko rozpowszechnione kłamstwo. Pokrywy włazów są okrągłe przede wszystkim dlatego, że zakrywają końce rur, a rury są okrągłe. Rury są okrągłe, ponieważ 1) równomiernie rozkłada na nie obciążenia oraz 2) maksymalizuje przekrój dla danego obwodu. Ogólnie rzecz biorąc, maksymalizuje wytrzymałość i pojemność rury, którą można uzyskać z określonej ilości materiału.

Jerry Coffin

@JerryCoffin: Więc ... drzewa rosną w dół, ponieważ okrągłe rury są silniejsze niż kwadratowe? ;)

FrustratedWithFormsDesigner

Odpowiedzi:

Tylko zgadnij:

Struktury drzew rosną w dół (korzeń u góry, liście u dołu), ponieważ ludzie czytają od góry strony w dół. Ponadto, jeśli narysujesz duże drzewo, które rozciąga się na kilku stronach, byłoby niezręcznie poprosić czytelnika, aby przeskoczył o kilka stron do przodu, a następnie pracował do tyłu.

Ponadto, niezależnie od tego, czy konwencja rozpoczęła się z powodu wyjaśnionego powyżej, czy z jakiegoś innego powodu, kontynuujemy praktykę dzisiaj właśnie dlatego, że jest to konwencja. Mamy odpowiednie terminy, takie jak węzeł najwyższego poziomu (co oznacza root), co nie miałoby większego sensu, gdybyśmy narysowali strukturę z rootem na dole.

Caleb
źródło

@BruceEdiger: Zgaduję, że sprowadza się to do różnych konwencji.

FrustratedWithFormsDesigner

@BruceEdiger To coś zupełnie innego. Układ współrzędnych kartezjańskich powstała 375 lat temu, więc to całkiem naturalne, aby trzymać się tej konwencji. Systemy graficzne (X11, QuickDraw, Quartz na iOS) często używają odwróconego układu współrzędnych. Nie sądzę jednak, żeby miało to związek z tym, jak rysujemy drzewa.

Caleb

IMHO przyczyna przerzucenia współrzędnych sięga czasów, w których jeden miał terminale. Ponieważ wyświetlały tekst zaczynający się od lewego górnego rogu, a rzeczywista rozdzielczość może się różnić, bardzo rozsądną decyzją było wybranie (0,0) lewego górnego rogu.

FUZxxl

@BruceEdiger współrzędne ekranowe zasadniczo mapują od (x, y) do lokalizacji w pikselach / znakach. Kontrolery wyświetlania wideo odpowiedzialne za mapowanie pamięci do obrazu zaczynają się w miejscu 0 w lewym górnym rogu. Dlatego naturalnym mapowaniem jest posiadanie (0,0), ponieważ można uzyskać lokalizację pamięci tylko za pomocą (y * 80 + x). Dokumentacja dla komputera 8-bitowego Nauczyłem się tego z: datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf

Podczas ręcznego rysowania drzewa trudno jest wiedzieć, ile miejsca będziesz potrzebować, trudno również starannie ułożyć notatki bez uprzedniego narysowania poziomu powyżej. Więc zwykle narysuj „root”, umieszczając go najpierw na górze, abyś mógł kontynuować pracę z tekstem, gdziekolwiek na stronie kończy się drzewo.

Ian

Konwencja wydaje się wynikać z algorytmu Coffmana-Grahama, który ma na celu:

„... do układania elementów częściowo uporządkowanego zestawu w sekwencji poziomów. Algorytm wybiera takie ustawienie, że element występujący po drugim w kolejności jest przypisywany do niższego poziomu, a każdy poziom ma numer elementów, który nie przekracza stałej szerokości związanej W. ”

Ich praca z 1972 r. ( PDF ) pokazuje ukierunkowany wykres acykliczny rysowany od góry do dołu. Jest to krótki krok do przedstawienia drzewa w ten sam sposób.

W tym artykule na temat warstwowego wykresu graficznego znajduje się dalszy komentarz do tej wizualizacji .

Gary Rowe
źródło

Sztuka programowania komputerowego: podstawowe algorytmy, tom 1 - podstawowe algorytmy, została opublikowana w 1968 roku i zawierała rozdział 2 o drzewach. Czy ktoś posiadający tę książkę może zweryfikować, czy diagramy pokazują rosnące drzewa? Jeśli tak, historia wskazuje na konwencję rozpoczętą jeszcze wcześniej. Zastanawiam się także, czy informatyka wzięła tę konwencję z matematyki jeszcze przed 1960

rokiem

@maxpolk Knuth rysuje swoje drzewa w sposób root-at-top i omawia swoją decyzję (rozdział 2.3, s. 311 w 3. wydaniu) o konwersji formy root-at-bottom przed publikacją pierwszego wydania. Sprowadza się to do „większości istniejącej literatury idzie z góry na dół i potrzebujemy spójnego modelu do celów dyskusji” (80% według ankiety Knutha).

Ross Patterson

Czerpiąc z top > downi left > rightsą popularne w informatyce, ponieważ są to początkowe kierunki w pisanym języku angielskim. Biorąc pod uwagę, że większość prac z zakresu informatyki jest napisana w języku angielskim, niezależnie od rodzimego języka pisarza, byłby to najbardziej rozpowszechniony sposób rysowania diagramów.

Dla czytelników języka angielskiego najbardziej naturalne jest odczytywanie wykresu z dowolnej innej alternatywy top > downlub left > rightz niej.

Przeszukaj images.google.com directed tree graphi przejrzyj wyniki. Jedyne drzewo schematy mogę znaleźć, że poszedł w górę były UML Diagramy klas, a tylko dlatego, że jest konwencja, że wybrał dla klasy UML diagramów. Wszystkie inne diagramy UML idą left > rightlub up > down.

Rozważałbym czytanie skierowanych wykresów drzew z down > uptak nienaturalnego, jak czytanie najczęściej wysyłanych wątków e-mail; co powiedzieć jest całkowicie nienaturalne.

źródło