Co oznacza „spłaszczanie”?

13

Gdybym miał drzewo, „spłaszczyłbym się” intuicyjnie

uzyskać listę wszystkich elementów w drzewie, przechodząc od lewej do prawej?

Jeśli mam połączoną listę, „spłaszczyłbym” się intuicyjnie

uzyskać listę wszystkich przedmiotów, zaczynając od tego

Na przykład połączona lista składałaby się z wyjątku, który agreguje wyjątek wewnętrzny. Czy sprawiedliwie byłoby nazwać metodę wyjątku „flattenInnerExceptions” z oczekiwaniem, że zwróci sekwencję wyjątków, najpierw skrajny wyjątek, a najbardziej wewnętrzny wyjątek - ostatni?

GregC
źródło

Odpowiedzi:

25

Gdybym miał listę list, „spłaszczenie” byłoby operacją, która zwraca listę wszystkich elementów liścia w kolejności, tzn. Coś, co się zmienia:

[[a, b, c], [d, e, f], [g, h i]]

W

[a, b, c, d, e, f, g, h, i]

W przypadku drzew wyrównywanie generuje listę wszystkich liści w naturalnym porządku przechodzenia (Uwaga: ponieważ wynikiem są tylko liście, nie ma znaczenia, czy myślisz o tym jako o przejściu przed, po lub po zamówieniu).

W konsekwencji dla prostej listy operacja „spłaszczenia” jest z definicji transformacją tożsamości.

Spłaszczanie można przeprowadzać etapami lub stopniami. Na przykład:

[[[a, b], [c, d]], [[e, f], [g, h]]]

można spłaszczyć do:

[[a, b, c, d], [e, f, g, h]]

a następnie do:

 [a, b, c, d, e, f, g, h]
Donal Fellows
źródło
@Donal Fellows: Odnosi się do połowy pytania o drzewa. Co z listami połączonymi? Czy mówienie o nich za pomocą terminu „Spłaszczanie” jest intuicyjne?
GregC,
@GregC, być może chciałbyś dodać przykład tego, co uważasz za połączoną listę.
Edytowałem pytanie na przykładzie.
GregC,
3
@GregC: Lista połączona jest tylko implementacją typu abstrakcyjnego sekwencji. (Tablica jest także implementacją tego typu abstrakcyjnego na co najmniej jednym poziomie, i tak, istnieją znaczne różnice; typy abstrakcyjne nie są całą historią.) Większość systemów alokacji pamięci sprawia, że ​​listy połączone są dość drogie, ponieważ „ ponownie płacę narzut za przydział pamięci na komórkę listy (ten narzut często ma około 8 bajtów w systemie 32-bitowym), więc nie zalecałbym ich używania, chyba że potrzebujesz ciągłego wstawiania i usuwania.
Donal Fellows
1
@BarisDemiray Tak. Byłby to wynik spłaszczenia pierwszego poziomu, a drugi byłby po dwóch rundach ...
Donal Fellows