Какова временная сложность Morris Traversal o (n)?

Ответ 1

он не будет увеличивать сложность, так как алгоритм просто перестраивает дерево только в одном направлении (перестройка занимает только O (n), после чего его только O (n) снова печатает их... но они объединили оба функциональность в одну и ту же функцию и дал специальное имя для этого алгоритма...

Ответ 2

Другой способ взглянуть на это - выяснить, сколько раз будет проходить дерево node. Поскольку он является постоянным (3 раза для двоичного дерева). Мы смотрим на O (n).

Ответ 3

Оригинальная бумага для обхода Морриса - это простое и дешевое перемещение бинарных деревьев. Он утверждает, что временная сложность O (n) во введении:

Он также эффективен, принимая время, пропорциональное количеству узлов в дереве, и не требует ни стопки во время выполнения, ни бит "флаг" в узлах.

Полный документ должен иметь анализ временной сложности. Но полную бумагу нельзя получить бесплатно.

Morris Traversal 方法 遍历 二叉树 (非 递归, 不用 栈, O (1) 空间) делает некоторый анализ. Я перевел часть релевантной части и внес некоторые исправления, основанные на моем понимании. Вот мое понимание:

Двоичное дерево n-узла имеет n-1 ребра. В обход Морриса один край посещают не более 3 раз. 1-ый визит - поиск узла. 2-й визит - поиск предшественника некоторого узла. И 3rd/final - для восстановления правильного дочернего элемента предшественника до нуля. В следующем двоичном дереве красная пунктирная линия предназначена для размещения узла (1-й визит). Черная пунктирная линия предназначена для поиска узла-предшественника (путешествует два раза: для второго посещения и третьего посещения). Узел F будет посещаться при его расположении. Он также будет посещаться, когда узел H ищет своего предшественника. Наконец, он будет посещен при восстановлении правильного дочернего элемента узла G (предшественник H) до нуля.

Ответ 4

Во-первых, у меня есть исправление, чтобы сделать выражение, которое вы сделали:

При обходе, когда у узла есть левый ребенок, его копия делается правым дочерним элементом своего предшественника

Копия [текущего] узла не сделана для правого дочернего элемента его предшественника [текущего узла] - правый дочерний элемент текущего предшественника узла указывает на текущий узел - указатель не производит никакой копии; вместо этого он просто указывает на текущий узел, который уже существует.

Теперь, чтобы ответить на ваш вопрос о фрагменте кода:

while(pre->right != NULL && pre->right != current)
        pre = pre->right;

• Этот цикл добавляет время к запуску алгоритма [по сравнению с тем, что этот цикл не был в коде]
• Но в худшем случае время, которое он добавляет, составляет ровно n (принимая время выполнения от n до 2n). Этот худший случай случается, когда каждый отдельный узел должен быть посещен в дополнительное время, чтобы найти всех предшественников; кстати, каждый такой дополнительный визит данного узла является единственным дополнительным временем его посещения при поиске предшественников (потому что поиск любого другого предшественника никогда не будет перемещаться по тем же узлам, которые были пройдены, чтобы найти любого другого предшественника) - это объясняет почему дополнительное время вносит вклад в n → 2n [linear], но не n → n ^ 2 [квадратично]
• Несмотря на то, что 2n> n, когда рассматривается сложность [Big-O], O (2n) = O (n)
• Другими словами, длительное время 2n по сравнению с n не является дополнительной сложностью: n & 2n runtimes имеют сложности одинакового O (n) [они оба являются "линейными"]

Теперь, хотя это может показаться, что я подразумевал выше, что весь алгоритм времени выполнения равен 2n, это не так - это фактически 3n.

• Цикл, который находится только в самом фрагменте кода, вносит n раз
• а затем 3-е/окончательное время, когда он снова будет найден как предшественник [это сам для второго/окончательного времени], а его указатель/поток справа-ребенка удаляется из указателя на правый дочерний узел текущего узла [непосредственно перед печатью текущего узла] }
• И снова [так же, как сложность O (2n) = O (n)], сложность O (3n) = O (n)
• Итак, чтобы подвести итог: да, ваш цикл фрагмента кода делает время, но НЕ лишняя временная сложность

Кстати, я не думаю, что эта строка (из полного алгоритма), чтобы удалить старую ссылку "поток" предшественника, строго необходима (хотя это не больно и может считаться хорошим убиранием):

pre->right = NULL;