Comments 28
Попробую максимально конструктивно
Мне кажется, что Вы упустили что дерево обходится без использования дополнительной памяти
Это важно при аварийной сборке мусора, например
Спасибо, натолкнули меня на мысль:
После аварийного прерывания алгоритма, например при потери питания, дерево все еще можно дообойти и расшить дерево до исходного состояния
Планирую обдумать и добавить апдейт в статью, естественно с благодарностью Вам за идею
Со своей стороны обязуюсь найти и описать алгоритм Морриса в отдельной статье, а также добавить обновление к данной статье со ссылкой на новую публикацию.
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 - сомневаюсь.
Обходить дерево с учётом глубины можно по-разному: можно сначала обходить корень, потом потомков, а можно, например, сначала левого, потом корень, потом правого. Второй вариант полезен, когда дерево отсортировано. Классический рекурсивный алгоритм легко адаптируется под эти варианты, авторский же жёстко реализует первый вариант.
Вчитываться не стал, но мне нравиться ход Вашей мысли)))
Можно будет попробовать привлечь Вас, как стороннего специалиста?
Извините за токсичное поведение
Попробую максимально конструктивно
Мне кажется, что Вы упустили что дерево обходится без использования дополнительной памяти
Это важно при аварийной сборке мусора, например
Спасибо, натолкнули меня на мысль:
После аварийного прерывания алгоритма, например при потери питания, дерево все еще можно дообойти и расшить дерево до исходного состояния
Планирую обдумать и добавить апдейт в статью, естественно с благодарностью Вам за идею
Мне кажется, что Вы упустили что дерево обходится без использования дополнительной памяти
Неудевительно, ведь вы очень плохо написали статью. Загловок:
Алгоритм полного левостороннего обхода узлов двоичного дерева
И в начале статьи ничего про дополнительную память тоже нет. Зато много про Вас любимого.
Слова "без использования дополнительной памяти" встречаются только в секции "Аппендикс А" про историю алгоритма, в которую ни один уважающий себя читатель вчитываться не будет. Их я нашел только сейчас поиском по странице.
Если бы вы статью озаглавили "Об обходе бинарных деревьев без использования дополнительной памяти", а в статье грамотно описали задачу и ограничения, указали, что да, есть алгоритм Морриса, но вы придумали вот это вот сами еще 30 лет назад, и оно вот в этих деталях отличается, поэтому достойно статьи, привели доказательства вместо исторической справки, то вам бы понаставили плюсов и даже возможно похвалили.
Возможно бы написли, что более корректно было бы "с использованием константной дополнительной памяти". Но это мелочь.
Кстати, даже сам Моррис свой алгоритм опубликовал в статье "Traversing binary trees simply and cheaply" (Обход бинарных деревьев просто и эффективно). А не "алгоритм Морриса". И так везде. Все вот эти "алгоритм Такого-то", ни один автор никогда своей фамилией не называл. Это дикая пошлось и зашкаливающее ЧСВ. Все просто ставили свою подпись под научными статьями. И уже только потом, признав их внушительный вклад, последователи стали называть эти алгоритмы их именами.
Так что если вам так чешется получить признание - опубликуйте статью в каком-нибудь журнале по computer science. Правда там придется гораздо серъезнее поработать над статьей. Вот то, что у вас написано сейчас, ни один журнал не примет.
Не уверен, что вы обращаетесь ко мне, наблюдаю проблемы в комментировании. Но попробую. Я не упустил, что дополнительной памяти не требуется, я это явно написал в своём комментарии. Не думаю, что это можно как-то применить при аварийной сборке мусора, потому что деревья не применяются при распределении памяти, плюс память освобождается проходом по графу ссылок, а ваш алгоритм не сработает для графов. Ну и для классического рекурсивного обхода требуется память на стеке, а не на куче.
Вы очень акцентируетесь на самом алгоритме, но проблема с ним в том, что он не очень полезен. Деревья применяют, когда, например, нужно что-то отсортировать: вставка несортированной коллекции в дерево имеет сложность n*log(n), зато потом можно итерироваться в порядке возрастания! Поэтому для алгоритма обхода очень важно, чтобы он происходил в порядке элементов: левосторонний обход идёт по возрастанию. А у вас не левосторонний обход. Вот у Морриса - да.
А вот тут уже конструктивней
Мой цифровой коллега подтвердил что в части алгоритмов чистки мусора используются бинарные деревья, что и до-того было мне известно
Надеюсь, вброшенный мной алгоритм вызовет волну интереса к технологиям сборки
Спасибо.
P.S. "Пилите, Шура, она золотая"
P.S. Я серьезно. Чую что-то ценное, доказать не могу)
Извините, Вы плохо прочитали коротенькую, простенькую преамбулу:
" Со своей стороны обязуюсь найти и описать алгоритм Морриса в отдельной статье, а также добавить обновление к данной статье со ссылкой на новую публикацию. До тех пор предлагаю называть «Алгоритмом Вахнина» 30-летнюю саму историю публикации описания алгоритма."
А в целом, продолжайте, пожалуйста. Мне нравится как растет количество просмотров. На это никакой кармы не жалко.
Lol
То, что алгоритм пишет в дерево, это большой недостаток. В моём понимании, алгоритмы обхода должны работать на read-only структурах.
Если взять дерево, в каждой ноде которого есть ссылка на родителя, то алгоритм обхода без дополнительной памяти очень простой. Представим, что дерево - это лабиринт, и можно его обойти, пользуясь правилом "правой руки". Дерево в этом случае не обязательно должно быть бинарным.
Расскажите, как вы на иммутабельных структурах построите дерево, в котором у нод есть ссылка на родителя?
Вы имеете ввиду, что иммутабельные структуры живут в куче? Так именно переполнение кучи желательно подстраховать аварийным сбором мусора
Предсказывать переполнение стека, вроде, уже умеем
Что мешает такие объекты прошить еще и как бинарные деревья?
Тут, возможно, Вы правы и заморачиваться нужно только в системах, для которых важна стабильность поведения. Ну там космические спутники. Не пошлешь же стажера в космос для жесткого ребута))
Не могу молчать))
А не увеличит ли данный механизм стоимость DDos атак?
как вы на иммутабельных структурах построите дерево, в котором у нод есть ссылка на родителя?
Ну вы поняли, что я имел ввиду доступ к структуре только на чтение в момент обхода.
А вообще, хороший вопрос. Элементарное решение: после построения классического дерева рядом построить индекс (хеш-таблицу) child → parent.
Алгоритм Вахнина