Geodesic
An estimate for the mean efficiency of search trees constructed for arbitrary sets of binary words
Diskretnaya Matematika, Tome 14 (2002) no. 1, pp. 142-150.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem on constructing a binary search tree for an arbitrary set of binary words, which has found a wide use in informatics, biology, mineralogy, and other fields. It is known that the problem on constructing the tree of minimal cost is NP-complete; hence the problem arises to find simple algorithms which allow us to construct trees close to the optimal ones. In this paper we demonstrate that even simplest algorithm yields search trees which are close to the optimal ones in average, and prove that the mean number of nodes checked in the optimal tree differs from the natural lower bound, the binary logarithm of the number of words, by no more than 1{.}04. This research was supported by the Russian Foundation for Basic Research, grant 98–01–00772. 
@article{DM_2002_14_1_a9,
     author = {B. Ya. Ryabko and A. A. Fedotov},
     title = {An estimate for the mean efficiency of search trees constructed for arbitrary sets of binary words},
     journal = {Diskretnaya Matematika},
     pages = {142--150},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_1_a9/}
}
TY  - JOUR
AU  - B. Ya. Ryabko
AU  - A. A. Fedotov
TI  - An estimate for the mean efficiency of search trees constructed for arbitrary sets of binary words
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 142
EP  - 150
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_1_a9/
LA  - ru
ID  - DM_2002_14_1_a9
ER  - 
%0 Journal Article
%A B. Ya. Ryabko
%A A. A. Fedotov
%T An estimate for the mean efficiency of search trees constructed for arbitrary sets of binary words
%J Diskretnaya Matematika
%D 2002
%P 142-150
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2002_14_1_a9/
%G ru
%F DM_2002_14_1_a9
B. Ya. Ryabko; A. A. Fedotov. An estimate for the mean efficiency of search trees constructed for arbitrary sets of binary words. Diskretnaya Matematika, Tome 14 (2002) no. 1, pp. 142-150. http://geodesic.mathdoc.fr/item/DM_2002_14_1_a9/

[1] Knut D., t. 3, Iskusstvo programmirovaniya na EVM, Mir, Moskva, 1976

[2] Alsvede R., Vegener I., Zadachi poiska, Mir, Moskva, 1982

[3] Krichevskii R. E., “Szhatie i poisk informatsii”, Radio i svyaz, 1989, Moskva | MR

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR