Szukam najbardziej wydajnego algorytmu do pobrania drzewa (przechowywanego jako lista krawędzi; LUB jako lista odwzorowań z węzła nadrzędnego na listę węzłów podrzędnych); i stworzyć dla KAŻDEGO węzła listę wszystkich węzłów z niego pochodzących (poziom liścia i poziom nie-liści).
Wdrożenie musi odbywać się za pomocą pętli zamiast recusion, ze względu na skalę; i idealnie powinien być O (N).
To pytanie SO obejmuje standardowe, dość oczywiste rozwiązanie, aby znaleźć odpowiedź na JEDEN węzeł w drzewie. Ale oczywiście powtarzanie tego algorytmu na każdym węźle drzewa jest wysoce nieefektywne (z góry mojej głowy, od O (NlogN) do O (N ^ 2)).
Korzeń drzewa jest znany. Drzewo ma absolutnie dowolny kształt (np. Nie jest N-nary, nie jest w żaden sposób zbalansowany, ma kształt lub formę, nie ma jednolitej głębokości) - niektóre węzły mają 1-2 dzieci, niektóre mają 30K dzieci.
Na poziomie praktycznym (choć nie powinno to wpływać na algorytm) drzewo ma ~ 100–200 000 węzłów.
źródło
Odpowiedzi:
Jeśli faktycznie chcesz PRODUKOWAĆ każdą listę jako różne kopie, nie możesz mieć nadziei, że w najgorszym przypadku uzyskasz miejsce większe niż n ^ 2. Jeśli potrzebujesz tylko DOSTĘPU do każdej listy:
Wykonałbym przemierzanie drzewa w kolejności zaczynając od korzenia:
http://en.wikipedia.org/wiki/Tree_traversal
Następnie dla każdego węzła w drzewie przechowuj minimalną liczbę zamówień i maksymalną liczbę zamówień w poddrzewie (można to łatwo utrzymać przez rekurencję - możesz to symulować za pomocą stosu, jeśli chcesz).
Teraz umieść wszystkie węzły w tablicy A o długości n, w której węzeł o numerze porządkowym i znajduje się w pozycji i. Następnie, gdy musisz znaleźć listę dla węzła X, spójrz na A [X.min, X.max] - zauważ, że ten przedział będzie obejmować węzeł X, który również można łatwo naprawić.
Wszystko to odbywa się w czasie O (n) i zajmuje przestrzeń O (n).
Mam nadzieję, że to pomoże.
źródło
Nieefektywną częścią nie jest przemierzanie drzewa, ale budowanie list węzłów. Wydaje się rozsądne stworzenie takiej listy:
Ponieważ każdy węzeł potomny jest kopiowany na listę każdego rodzica, w przypadku drzew zrównoważonych uzyskujemy średnio złożoność O (n log n) i najgorszy przypadek O (n²) w przypadku drzew zdegenerowanych, które są naprawdę połączonymi listami.
Możemy upaść na O (n) lub O (1) w zależności od tego, czy musisz przeprowadzić konfigurację, jeśli wykorzystamy sztuczkę leniwego obliczania list. Załóżmy, że mamy plik,
child_iterator(node)
który daje nam dzieci tego węzła. Następnie możemy w prosty sposób zdefiniować cośdescendant_iterator(node)
takiego:Rozwiązanie nierekurencyjne jest o wiele bardziej zaangażowane, ponieważ przepływ sterowania iteratorem jest trudny (coroutines!). Zaktualizuję tę odpowiedź później dzisiaj.
Ponieważ przejście do drzewa wynosi O (n), a iteracja po liście jest również liniowa, sztuczka całkowicie odracza koszt, dopóki i tak nie zostanie zapłacony. Na przykład wydruk listy potomków dla każdego węzła ma złożoność najgorszego przypadku O (n²): iteracja po wszystkich węzłach to O (n), podobnie jak iteracja po potomkach każdego węzła, niezależnie od tego, czy są one przechowywane na liście, czy obliczone ad hoc .
Oczywiście to nie zadziała, jeśli potrzebujesz rzeczywistej kolekcji do pracy.
źródło
Ten krótki algorytm powinien to zrobić, spójrz na kod
public void TestTreeNodeChildrenListing()
Algorytm faktycznie przechodzi kolejno przez węzły drzewa i prowadzi listę rodziców bieżącego węzła. Zgodnie z wymaganiami bieżący węzeł jest dzieckiem każdego węzła nadrzędnego, który jest dodawany do każdego z nich jako dziecko.
Ostateczny wynik jest przechowywany w słowniku.
źródło
Zwykle wystarczy zastosować podejście rekurencyjne, ponieważ pozwala ono na zmianę kolejności wykonywania, dzięki czemu można obliczyć liczbę liści zaczynając od liści w górę. Ponieważ musisz użyć wyniku wywołania rekurencyjnego, aby zaktualizować bieżący węzeł, przygotowanie wersji rekurencyjnej wymagałoby specjalnego wysiłku. Jeśli nie podejmiesz tego wysiłku, to oczywiście takie podejście po prostu rozbije Twój stos dla dużego drzewa.
Biorąc pod uwagę, że zdaliśmy sobie sprawę, że główną ideą jest uzyskanie kolejności zapętlania, zaczynając od liści i wracając do korzenia, naturalną ideą, która przychodzi na myśl, jest wykonanie sortowania topologicznego na drzewie. Wynikową sekwencję węzłów można przesuwać liniowo, aby zsumować liczbę liści (zakładając, że można zweryfikować, że węzeł jest liściem w
O(1)
). Ogólna złożoność czasowa rodzaju topologicznego wynosiO(|V|+|E|)
.Zakładam, że twoja
N
jest liczbą węzłów, która|V|
zwykle byłaby (z nomenklatury DAG). ZE
drugiej strony wielkość zależy w dużej mierze od aromatu twojego drzewa. Na przykład drzewo binarne ma co najwyżej 2 krawędzie na węzeł, dlategoO(|E|) = O(2*|V|) = O(|V|)
w takim przypadku powstałby ogólnyO(|V|)
algorytm. Pamiętaj, że ze względu na ogólną strukturę drzewa nie możesz mieć czegoś takiegoO(|E|) = O(|V|^2)
. W rzeczywistości, ponieważ każdy węzeł ma unikalny element nadrzędny, możesz mieć co najwyżej jedną krawędź do zliczenia na węzeł, jeśli weźmiesz pod uwagę tylko relacje nadrzędne, więc dla drzew mamy taką gwarancjęO(|E|) = O(|V|)
. Dlatego powyższy algorytm ma zawsze liniowy rozmiar drzewa.źródło