Поздравляю Эдуарда Владимировича Ильченко, создавшего эту важную тему и инициировавшего обсуждение.
Эта инициатива имела важное продолжение.
Прочитав данное обсуждение В.И. Шелехов вдохновился, получил грант Российского фонда фундаментальных исследований и написал статью:
Заключение
Предпосылкой появления данной работы стала дискуссия на форуме [3] о том, какая из программ вставки в АВЛ-дерево лучше: на языке Оберон или графическом языке Дракон [6].
Эргономические методы, применяемые в языке Дракон, существенно улучшают восприятие программы.
Тем не менее, программа не выглядит проще. Причина – исходная сложность императивной программы.
Методы предикатного программирования: использование рекурсивных программ вместо циклов, алгебраических типов вместо указателей и др. позволяют в несколько раз снизить сложность программы по сравнению с аналогичной императивной программой, в частности с программами на форуме [3].
Доступ к вершине дерева реализован через указатель на поле (в некоторой вершине), в котором хранится ссылка на требуемую вершину. При передаче через параметр программы возникает двойной указатель.
В описании библиотеки libavl [2] используется однократный указатель, однако при этом дополнительно поддерживается указатель на предыдущую вершину-отца.
Как следствие, алгоритм получается более громоздким и менее эффективным в сравнении с приведенным в настоящей работе.
В нашей версии, тем не менее, для каждого двойного указателя заводится соответствующий одинарный. Реализация такой техники в трансформациях может оказаться нетривиальным.
Поэтому в начальном релизе следует ограничиться только двойным указателем.
Работа выполнена при поддержке РФФИ, грант № 12-01-00686.
Литература
1. Википедия. АВЛ-дерево.
http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B2%D0%BE 2. Ben Pfaff. GNU libavl 2012. An Introduction to Binary Search Trees and Balanced Trees.
ftp://ftp.gnu.org/pub/gnu/avl/avl-2.0.2.pdf.gz 3. АВЛ-дерево. Алгоритм добавления вершины.
viewtopic.php?f=78&t=40034. R. Hettler, D. Nazareth, F. Regensburger, O. Slotosch. AVL trees revisited: A case study in Spectrum. LCNS, vol. 1009, 1995, pp 128-147.
5. AVL Tree in Haskell.
https://gist.github.com/gerard/109729 6. Паронджанов В. Д. Язык ДРАКОН. Краткое описание. — М., 2009. — 124 с.
7. Карнаухов Н.С., Першин Д.Ю., Шелехов В.И. Язык предикатного программирования P. Версия 0.12 — Новосибирск, 2013. — 52с.
http://persons.iis.nsk.su/files/persons ... lang12.pdf8. Каблуков И. В. Реализация оптимизирующих трансформаций предикатных программ // XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Томск, 2013. 7с.
http://conf.nsc.ru/files/conferences/ym ... 69/177104/Опт.%20трансформации.pdf
Читать дальше ...