Encoding Trees by Linear Recurrence Sequences
- PDF / 155,610 Bytes
- 12 Pages / 594 x 792 pts Page_size
- 51 Downloads / 227 Views
ENCODING TREES BY LINEAR RECURRENCE SEQUENCES
A. V. Anisimov
UDC 519.7
Abstract. A unified encoding of ordered binary trees with integer-valued labels at their vertices is proposed using linear forms of neighboring members of linear recursive sequences of the form Pn + 2 = a n + 2 Pn + 1 + Pn , where P1 = P2 = 1; a 3 and a 4 K are natural numbers. Encoding and decoding procedures are simply implemented and use the recursive technique of direct pre-order depth-first tree traversal. A brief review of possible applications of the proposed encoding in problems of tree processing and cryptographic symmetric encryption is presented. Keywords: binary tree, encoding tree, linear recurrent sequence, Fibonacci number. INTRODUCTION Modern technologies of transmission, storage, and protection of information are mainly focused on numerical representations of data. At the same time, by its nature, information mainly has a complex structure. Therefore, a universal numeric encoding of such structures is one of topical problems of the current stage of developing information and communication technologies. The universal encoding of ordered trees by natural numbers, which is proposed in this work, is aimed at the solution of this problem. Trees form one of the most important data structures, which is widely applied in numerous computer algorithms. Therefore, their numeric encoding is of considerable interest. At present, this interest is also motivated by intensive investigations in the field of chemistry and biology aimed at finding similar molecular and taxonomic structures with the use of hierarchical representation models. Encoding undirected trees using sequences of numerical vertex labels is well known. H. Pr&& ufer [1] was one of the first to apply a similar encoding to prove the Cayley theorem on the number of undirected trees with n vertices. Subsequently, many improved algorithms of this type appeared [2–4]. The Pr&& ufer encoding presumes that all vertex labels are different and that the code itself of a tree consists of the sequence of all labels ordered in a special way. Of theoretical interest is a one-to-one correspondence between unordered root trees and natural numbers, which is based on the decomposition of numbers into the product of prime numbers (the Matula–Goebel bijection) [5, 6]. There are many ways to represent ordered root trees (ordinal trees) in the form of special numerical sequences. Among them are representations using level numbers of leaves enumerated from left to right, various sequences of labels reflecting the order of traversal of a vertex (pre-order tree traversal), and parenthesis 0–1 strings of binary trees. A review of methods of generation of trees using their representations in the form of numerical sequences is given by D. Knuth in [7]. We are interested in representing a tree in the form of one number. As is obvious, using Cantor’s numbering, any sequence of numbers can be represented biuniquely by one number. Therefore, any numerical sequence encoding the structure of a tree can theore
Data Loading...
