The estimated cost of a search tree on binary words

Citation
A. Fedotov et B. Ryabko, The estimated cost of a search tree on binary words, IEEE INFO T, 47(1), 2001, pp. 326-329
Citations number
4
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
IEEE TRANSACTIONS ON INFORMATION THEORY
ISSN journal
0018-9448 → ACNP
Volume
47
Issue
1
Year of publication
2001
Pages
326 - 329
Database
ISI
SICI code
0018-9448(200101)47:1<326:TECOAS>2.0.ZU;2-U
Abstract
The problem of constructing a binary search tree for a set of binary words has wide applications in computer science, biology, mineralogy, etc. Shanno n considered a similar statement in his optimal coding theorem. It is NP.-c omplete to construct a tree of minimum cost [4]; therefore, the problem ari ses of finding simple algorithms for constructing nearly optimal trees. We show in this correspondence that there is a simple algorithm for constructi ng search trees sufficiently close to the optimal tree on average. By means of this algorithm we prove that for the optimal tree the average number of bits to be checked is near to its natural lower bound, i.e., the binary lo garithm of the number of given words: their difference is less than 1.04.