Comments 13
Со своей стороны обязуюсь найти и описать алгоритм Морриса в отдельной статье, а также добавить обновление к данной статье со ссылкой на новую публикацию.
https://habr.com/ru/companies/piter/articles/836280/
https://www.geeksforgeeks.org/dsa/inorder-tree-traversal-without-recursion-and-without-stack/
https://fcodenotes.ru/izuchenie-obhoda-poryadka-morrisa-v-python-podrobnoe-rukovodstvo/
https://russianblogs.com/article/34421113638/
https://pythobyte.com/morris-pre-order-tree-traversal-332b-e0b1b1ef/
Спасибо за сырую попытку погасить мой технический долг
Суть долга это взять оригинальную статью Морриса, и переписать в духе этой статьи
Этим я докажу приоритет изобретения (это совсем другой алгоритм) и продолжу стряхивать пыль с теории алгоритмов, как отрасли
Увы, статья на хабре не доказывает приоритет и тем более тот факт, что это изобретение.
Полагаю, что приоритет надо доказывать патентом , либо датой первой публикации и доказательством преимущества данного алгоритма относительно известных.
Спасибо за конструктивную критику, позволяющею мне поумничать)))
Есть приоритет изобретения и есть приоритет публикации
Естественно, собираюсь переписать статью для академического издания
А вот патентом заниматься не охото от слова совсем
Если хотите, можете попробовать потестировать патентную среду. Да хоть с "алгоритмом Иванова"))))))))))
А почему так скромно? Почему сложность материала поставили "средний" а не "сложный"? По вашим же словам, алгоритм был придуман за 15 лет до вашего изобретения, плюс вы его потом еще 30 лет вынашивали перед публикацией. Называть его своей фамилией - весьма нагло.
Далее, этот алгоритм - это нерекурсивный обход дерева? Это интересная задача, но много раз уже решенная и широко известная. Помимо уже упомянутого алгоритма Морриса, можно использовать стек.
Далее, раз уж вы описываете алгоритм, то извольте привести и доказательство того, что он правильно работает, а так же оценку сложности. Мы же тут все-таки наукой занимаемся, а не на стене в туалете стихи пишем.
Это добавит забавный штрих в теорию алгоритмов: левосторонний — Вахнина, правосторонний — Иванова
Какая пошлость.
Ну и кстати, если вы без ИИ написать статью не можете, может не доросли вы еще свое имя в анналы computer science записывать?
Классический рекурсивный обход дерева в глубину прост и понятен. Автор же изобрёл вариант обхода дерева без вызовов и возвратов. Вместо этого он перестраивает дерево, чтобы по нему постоянно можно было спускаться, каждый раз пропихивая правую подветвь в самые глубины левой подветви. Возьмём элементарный пример: дерево из трёх узлов, корень R с левым A и правым B потомками. Алгоритм автора добавит узлу А левый потомок "Marker", а узел B переместит как правого потомка узла А. По памяти overhead-а нет, в слоты, где были null-ы, запишутся ссылки. Насколько я представляю, лево-вырожденное дерево и право-вырожденное дерево не потребуют перемещений вообще, а сбалансированное дерево глубины n потребует n перемещений. Поиск того узла, куда прицепить бывшую правую ветвь, тоже с линейной зависимостью от глубины. Поскольку глубина в среднем - логарифм от количества узлов, то с точки зрения оценки стоимости эти перемещения ничего не добавляют, итоговая стоимость обхода будет линейная. Стоит ли этот огород отказа от return - сомневаюсь.
Обходить дерево с учётом глубины можно по-разному: можно сначала обходить корень, потом потомков, а можно, например, сначала левого, потом корень, потом правого. Второй вариант полезен, когда дерево отсортировано. Классический рекурсивный алгоритм легко адаптируется под эти варианты, авторский же жёстко реализует первый вариант.
Алгоритм Вахнина