The estimated cost of a search tree on binary words

被引：3

作者：

Fedotov, A ^{[1
]}

Ryabko, B

机构：

[1] Inst Computat Technol, Dept Informat Technol, Novosibirsk 90, Russia

[2] Siberian State Univ Telecommun & Informat Sci, Dept Appl Math & Cybernet, Novosibirsk 102, Russia

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2001年 / 47卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

binary tree; search tree; Shannon theorem;

D O I：

10.1109/18.904530

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The problem of constructing a binary search tree for a set of binary words has wide applications in computer science, biology, mineralogy, etc. Shannon considered a similar statement in his optimal coding theorem. It is NP.-complete to construct a tree of minimum cost [4]; therefore, the problem arises of finding simple algorithms for constructing nearly optimal trees. We show in this correspondence that there is a simple algorithm for constructing 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 logarithm of the number of given words: their difference is less than 1.04.

引用

页码：326 / 329

页数：4