Алгоритм кодирования бинарного дерева с минимальной избыточностью

Предложен алгоритм кодирования и декодирования бинарных деревьев с минимальной избыточностью, т. е. использующий битовые последовательности минимально возможной длины. Рекурсивное вычисление индексов деревьев выполнено с использованием чисел Ката-лана. Приведены оценки сложности алгоритма. Разработанный метод позволяет построить бинарное дерево на основе уникального индекса его структуры и числа узлов без необходимости явного перечисления всех возможных структур деревьев. Минимальная длина битовой последовательности дает возможность оптимизировать деревья с заданным числом узлов с помощью генетических алгоритмов.

Литература

[1] Корвяков В.П. Метод нейро-нечеткой оценки пригодности использования графического интерфейса пользователя // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 5. С. 61-74. DOI: 10.18698/0236-3933-2016-5-61-74

[2] Кнут Д. Искусство программирования. Т. 1. Основные алгоритмы / пер. с англ. М.: Вильямс, 2006. 720 с.

[3] Davis T. Catalan numbers // geometer.org: веб-сайт. URL: http://www.geometer.org/mathcircles/catalan.pdf (дата обращения: 17.08.2016).

[4] Bege A., Kasa Z. Coding objects related to Catalan numbers // Studia Universitatis Babes-Bolyai. Informatica. 2001. Vol. 46. No. 1. P. 31-40. URL: http://www.cs.ubbcluj.ro/~studia-i/2001-1/3-Kasa.pdf

[5] Flajolet P., Sedgewick R. Analytic combinatorics. Cambridge University Press, 2009. 826 p.

[6] Farzan A., Munro J.I. A uniform paradigm to succinctly encode various families of trees // Algorithmica. 2014. Vol. 68. No. 1. P. 16-40. DOI: 10.1007/s00453-012-9664-0 URL: http://link.springer.com/article/10.1007%2Fs00453-012-9664-0

[7] Davoodi P., Raman R., Satti S.R. On succinct representations of binary trees // arXiv.org: Cornell University Library. URL: http://arxiv.org/abs/1410.4963 (дата обращения: 29.09.2016).

[8] Makinen E. A survey on binary tree coding // The Computer Journal. 1991. Vol. 34. No. 5. P. 438-443. DOI: 10.1093/comjnl/34.5.438 URL: https://academic.oup.com/comjnl/article-abstract/34/5/438/553944/A-Survey-on-Binary-Tree-Codings?redirectedFrom=fulltext

[9] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / пер. с англ. М.: Вильямс, 2013. 1328 с.

[10] Catalantree - Binary trees decoding/encoding with Catalan numbers based algorithm // GitHub: веб-сайт. URL: https://github.com/HapKoM/catalantree (дата обращения: 24.08.2016).

[11] Gansner E., Koutsofios E., North E. Drawing graphs with dot // Graphviz: веб-сайт: http://www.graphviz.org/Documentation/dotguide.pdf (дата обращения: 24.08.2016).

[12] Кнут Д. Искусство программирования. Т. 4. Вып. 4. Генерация всех деревьев. История комбинаторной генерации / пер. с англ. М.: Вильямс, 2007. 160 с.