Thresholds and optimal binary comparison search trees |
| |
| Authors: | Richard Anderson Sampath Kannan Howard Karloff Richard E Ladner |
| |
| Institution: | a Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA 98195, USA;b AT&T Labs Research and Department of CIS, University of Pennsylvania, Philadelphia, PA 19104, USA;c AT&T Labs–Research, Room C231, Florham Park, NJ 07932, USA;d College of Computing, Georgia Institute of Technology, 801 Atlantic Dr., Atlanta, GA 30332-0280, USA |
| |
| Abstract: | We present an O(n4)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n5) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
