http://geeksforgeeks.org/?p=6358 Czy ktoś może wyjaśnić, jak Morris Traversal ma złożoność czasową o(n)? Podczas przemierzania, gdy węzeł ma lewe dziecko, jego kopia jest tworzona na prawe dziecko jego poprzednika. Tak więc najgorszy przypadek polega na tym, że poprzednika należy szukać w każdym węźle, aby zwiększyć złożoność? Czy brakuje mi tu czegokolwiek?Jaka jest złożoność Morris Traversal o (n)?
nie zwiększy to złożoności, ponieważ algorytm odbudowuje drzewo tylko w jednym kierunku (przebudowanie zajmuje tylko O (n), po którym jest tylko O (n), aby je wydrukować ... ale połączyły się zarówno funkcje do tej samej funkcji i dał specjalną nazwę dla algo to jest ...
Innym sposobem na to, aby zobaczyć, ile razy węzeł drzewa będzie wykonywany. Jak to jest stała (3 . czasy dla binarnego drzewa) Patrzymy na o (n)
Oryginalny papier do przechodzenia jest Traversing binary trees simply and cheaply Morris twierdzi, że czas złożoność wynosi o (n) w rozdziale Wstęp..
Jest także efektywny, zabierając czas proporcjonalny do liczby węzłów w drzewie i nie wymagając ani stosu w czasie rzeczywistym, ani "flag" bitów w węzłach.
Pełny artykuł powinien zawierać analizę złożoności czasowej. Ale pełny dokument nie może być dostępny za darmo.
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） dokonuje pewnych analiz. Jest to tłumaczenie odpowiedniej części:
N-węzłowe drzewo binarne ma krawędzie n-1. W przejściu Morrisa jedna krawędź jest odwiedzana najwyżej 2 razy. Jedna wizyta dotyczy lokalizacji węzła. Jedna wizyta dotyczy szukania poprzednika jakiegoś węzła. W poniższym drzewie binarnym czerwona linia przerywana służy do lokalizowania węzła. Czarna przerywana linia służy do wyszukiwania poprzedniego węzła.
sobie sprawę, że znalezienie poprzednik dla wszystkich węzłów w binarnym drzewie zajmie czas O (n) ... –