Во-первых, у меня есть исправление, чтобы сделать заявление, которое вы сделали:
При обходе, когда у узла есть левый потомок, его копия делается правому потомку егоПредшественник
Копия узла [current] имеет значение , а не , сделанное правому дочернему элементу предшественника [текущего узла] - правый дочерний элемент предшественника текущего узла равен указал на текущий узел - указатель не делает никакой копии;вместо этого он просто указывает на текущий узел, который уже существует .
Теперь, чтобы ответить на ваш вопрос о вашем фрагменте кода:
while(pre->right != NULL && pre->right != current)
pre = pre->right;
- Этот цикл добавляет добавление времени к выполнению алгоритма [по сравнению с тем циклом, которого не было в коде]
- Но в худшем случае время, которое он добавляет, равно n (принимая время выполнения от n до 2n ).Этот наихудший случай случается, когда каждый отдельный узел должен посещаться в дополнительное время, чтобы найти всех предшественников;кстати, каждое такое дополнительное посещение данного узла - это только дополнительное время, которое он посещает при поиске предшественников (это потому, что обнаружение любого другого предшественника никогда не будет проходить через те же узлы, которыепрошли через, чтобы найти любого другого предшественника) - это объясняет, почему дополнительное время способствует переходу от n -> 2n [линейный], но не n -> n ^ 2 [квадратичный]
- Даже если 2n > n , когда рассматривается [Big-O] сложность , O (2n) = O (n)
- Другими словами, более длительное время, равное 2n по сравнению с n , не является действительно дополнительным сложность : n & 2n время выполнения оба имеют сложности одинаковых O (n) [они оба "линейны"]
Теперь, хотя это могло звучать так, как я уже говорил выше, что весь алгоритм время выполнения равно 2n , это не так - это на самом деле 3n .
- Цикл, который находится в только фрагмент кода сам вносит n время
- Но алгоритм в целом работает в 3n потому что каждый узел посещается не более 3 раз (один раз / сначала, чтобы «нанизывать» его обратно на узел, для которого он является предшественником (конечная цель, которой помогает фрагмент кода);2-й раз, когда он достигается в обычном обходе [в отличие от чего-либо, что связано с потоковой обработкой предшественника];и затем 3-й / последний раз, когда он снова обнаруживается как предшественник [который сам на 2-й / последний раз] снова и его правый дочерний указатель / поток удаляется из указания на правый дочерний элемент текущего узла [непосредственно перед печатью текущего узла]}
- И снова [точно так же, как сложность O (2n) = O (n)], сложность O (3n) = O (n)
- Итак, подведем итог: Да, ваш цикл фрагмента кода вносит время , но НЕ дополнительное время сложность
Между прочим, я не думаю, что эта строка (из полного алгоритма) для удаления старой ссылки на «нить» предшественника является строго необходимой (хотя это не повредит, и может считаться хорошим исправлением):
pre->right = NULL;