Huffman trees and Fibonacci numbers. (English. Russian original) Zbl 0656.68066
Cybernetics 22, No. 6, 692-696 (1986); translation from Kibernetika 1986, No. 6, 9-12 (1986).
The author considers sequences of various types that minimize weighted path length of an elongated left-sided binary tree. He shows that such sequences may be expressed by Fibonacci sequence and he finds the corresponding weighted path length.
Reviewer: M.Frumkin
Online Encyclopedia of Integer Sequences:
a(n) = Fibonacci(n) - 3. Number of total preorders.Convolution of natural numbers >= 2 and Fibonacci numbers.
References:
| [1] | D. Knute, Art of Programming for Electronic Computers. Fundamental Algorithms [Russian translation], Vol. 1, Mir, Moscow (1976). |
| [2] | E. Rheingold, U. Nivergelt, and N. Deo, Combinatorial Algorithms. Theory and Practice [Russian translation], Mir, Moscow (1980). |
| [3] | A. Renyi, On the Mathematical Theory of Trees. Trilogy on Mathematics [Russian translation], Mir, Moscow (1980), pp. 353?375. |
| [4] | A. Renyi, Variations on a Theme of Fibonacci. Trilogy on Mathematics [Russian translation], Mir, Moscow (1980), pp. 326?352. |
| [5] | N. N. Vorob’ev, Fibonacci Numbers [in Russian], Nauka, Moscow (1984). |
| [6] | A. Berztiss, Data Structure [in Russian], Statistika (1974). |
| [7] | A. B. Vinokur and G. P. Kozhevnikova, ?On a class of regular trees used in the complexity analysis of algorithms,? preprint No. 82-18, Inst. Kibern., Akad. Nauk, Ukr. SSR, Kiev (1982). |
| [8] | A. B. Vinokur and G. P. Kozhevnikova, ?Approach to the formalization of an estimate of the efficiency of programmed transformations on the basis of an analysis of the properties of algorithms and data structures,? Optimization and Transformation of Programs: Materials of an All-Union Seminar (Novosibirsk, 1983) [in Russian], Vol. 1, 67?75, Vychisl. Tsentr. Sib. Otd. Akad. Nauk SSSR, Novosibirsk (1983). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
