Authors

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.