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

13 / 14

Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3 45
Abstract Keywords
This paper proposes an algorithm of binary trees enco-
ding and decoding with minimum redundancy, i. e. with
bit sequences of minimal possible length. We performed
recursive computation of trees indices using Catalan
numbers. Moreover, we give the algorithm complexity
estimations. The developed method allows us to construct
a binary tree on the basis of unique index of its structure
and number of nodes without explicitly enumerating all
possible tree structures. The minimal length of the bit
sequence makes it possible to optimize trees with the
fixed nodes number using genetic algorithms
Binary tree, Catalan numbers, enco-
ding algorithm, minimal redundancy
REFERENCES
[1] Korvyakov V.P. Method of neuro-fuzzy estimation of graphical user interface usability. Vestn.
Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech.
Univ., Instrum. Eng.], 2016, no. 5, pp. 61−74 (in Russ.). DOI: 10.18698/0236-3933-2016-5-61-74
[2] Knuth D.E. The art of computer programming. Vol. 1. Fundamental Algorithms. Reading,
Massachusetts: Addison-Wesley, 1997. 650 p.
[3] Davis T. Catalan numbers. : website. Available at:
mathcircles/catalan.pdf (accessed 17.08.2016).
[4] Bege A., Kasa Z. Coding objects related to Catalan numbers. Studia Universitatis Babes-Bolyai.
Informatica, 2001, vol. 46, no. 1, pp. 31–40. Available at:
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. Algo-
rithmica, 2014, vol. 68, no. 1, pp. 16–40. DOI: 10.1007/s00453-012-9664-0 Available at:
[7] Davoodi P., Raman R., Satti S.R. On succinct representations of binary trees. arXiv.org: Cornell
University Library. Available at: (accessed 29.09.2016).
[8] Mäkinen E. A survey on binary tree coding. The Computer Journal, 1991, vol. 34, no. 5,
pp. 438–443. DOI: 10.1093/comjnl/34.5.438 Available at:
article-abstract/34/5/438/553944/A-Survey-on-Binary-Tree-Codings?redirectedFrom=fulltext
[9] Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to algorithms. MIT Press,
2009. 235 p.
[10] Catalantree — Binary trees decoding/encoding with Catalan numbers based algorithm.
GitHub: website. Available at: (accessed 24.08.2016).
[11] Gansner E., Koutsofios E., North E. Drawing graphs with dot. Graphviz: website. Available at:
(accessed 24.08.2016).
[12] Knuth D.E. The art of computer programming. Vol. 4. Fascicle 4: Generating all trees–history
of combinatorial generation. Upper Saddle River, New Jersey, Addison-Wesley, 2011.
883 p.