On the max-entropy rule for a binary search tree |
| |
| Authors: | Yasuichi Horibe Tibor O H Nemetz |
| |
| Affiliation: | (1) Department of Information Sciences, Faculty of Engineering, Shizuoka University, Johoku 3-5-1, Hamamatsu, Japan;(2) Mathematical Institute of the Hungarian Academy of Sciences, Reáltanoda u. 13-15, 1053 Budapest, Hungary |
| |
| Abstract: | Summary A modified max-entropy rule is proposed for constructing nearly optimum binary search tree in the case of ordered keys with
given probabilities. The average cost of the trees obtained by this rule is shown to be bounded by the entropy of the probability
distribution plus a constant not larger than one. An algorithm for implementing this rule is then suggested and its complexity
is investigated in a probabilistic setting. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
