sprawdzić czy 2 drzewa węzły są związane (przodek/potomek) w czasie O (1) wstępnego przetwarzania

Question

sprawdzić czy 2 drzewa węzły są związane (tj przodek-potomek)

• go rozwiązać w czasie O (1) razem z o (N), przestrzeń (N = # węzłów)
• wstępne przetwarzanie jest dozwolone

koniec. Podejdę do mojego rozwiązania (podejścia) poniżej. Przestań, jeśli najpierw chcesz się pomyśleć.

---

Dla wstępnego przetwarzania postanowiłem zrobić wstępne zamówienie (rekursywnie przejść przez korzenia, potem dzieci) i nadać etykietę do każdego węzła.

Wytłumaczę etykiety w szczegółach. Każda etykieta będzie składać się z oddzielonych przecinkami liczb naturalnych, takich jak "1,2,1,4,5" - długość tej sekwencji równa się (głębokość węzła + 1). Na przykład. etykieta korzenia to "1", dzieci korzenia będą miały etykiety "1,1", "1,2", "1,3" itd. Następujące poziomy węzłów będą miały etykiety takie jak "1,1,1" , "1,1,2", ..., "1,2,1", "1,2,2", ...

Załóżmy, że "numer zamówienia" węzła jest "Oparty na jednym indeksie tego węzła" na liście dzieci jego rodzica.

Ogólna reguła: etykieta węzła składa się z etykiety nadrzędnej, po której następuje przecinek i "numer porządkowy" węzła.

Dlatego, aby odpowiedzieć, jeśli dwa węzły są związane (tj przodek-potomek) w czasie O (1), będę sprawdzenie czy etykieta z jednym z nich jest „prefiks” z drugiej na etykiecie. Chociaż nie jestem pewien, czy takie etykiety można uznać za zajmujące przestrzeń O (N). Oczekuje się

Wszelkie krytycy z poprawek lub alternatywnego podejścia.

Answer 1

Można to zrobić w czasie O (n) czasie przerób i O (n) przestrzeń, z O (1) czas zapytań, jeśli zapisać numer preorder i numer postorder dla każdego wierzchołka i wykorzystać ten fakt:

Dla dwóch podanych węzłów x i y drzewa T, x jest przodkiem y if i tylko wtedy, gdy x występuje przed y w trajektorii przed premierą T i po y podczas przejścia po zamówieniu.

(Od tej strony: http://www.cs.arizona.edu/xiss/numbering.htm)

Co robiłeś w najgorszym przypadku jest Theta (d), gdzie d jest głębokość wyższej węzła, a więc nie jest O (1). Przestrzeń również nie jest O (n).

Answer 2

Istnieje czas liniowy najmniejszy wspólny przodek algorytmy (przynajmniej w trybie off-line). Na przykład spójrz na here. Możesz również rzucić okiem na tarjan's offline LCA algorithm. Pamiętaj, że te artykuły wymagają znajomości par, z których będziesz wykonywał LCA z góry. Wydaje mi się, że istnieją również algorytmy czasu antenowego do obliczeń liniowych online, ale są one bardzo złożone. Na przykład istnieje liniowy algorytm czasu przedliczania dla zakresu minimalnego problemu zapytania. O ile pamiętam, to rozwiązanie dwukrotnie przechodziło przez problem LCA.Problem z algorytmem polega na tym, że ma on tak dużą stałą, że wymaga ogromnego sygnału wejściowego, aby był rzeczywiście szybszy niż algorytm O (n * log (n)).

Istnieje znacznie prostsze podejście, które wymaga O (n * log (n)) dodatkowej pamięci i ponownie odpowiada w stałym czasie.

Mam nadzieję, że to pomoże.

Answer 3

jeśli drzewo, w którym węzeł drzewa ma n/2 dzieci (na przykład), czas działania ustawień będzie równy O (n * n). Tak więc ten schemat etykietowania nie będzie działał ...