Name
Abstract | ||
|---|---|---|
Split trees are a technique for storing records with fixed frequency distributions. It was previously believed that no polynomial time algorithms to construct optimal representations of split trees were likely (B. A. Sheil, Median split trees: A fast lookup technique for frequently occurring keys, Comm. ACM (1978), p.949). In this paper we present an O(n5) algorithm to construct optimal binary split trees. Other efficient algorithms to construct suboptimal split trees are also discussed. The definition of split trees is later generalized to a larger class of trees so that we can compare several important classes of trees. |
Year | DOI | Venue |
|---|---|---|
1984 | 10.1016/0196-6774(84)90041-5 | Journal of Algorithms |
Field | DocType | Volume |
Discrete mathematics,Geometry of binary search trees,Combinatorics,Algorithm complexity,Fixed frequency,Weight-balanced tree,Time complexity,Binary search tree,Mathematics,Binary number | Journal | 5 |
Issue | ISSN | Citations |
1 | 0196-6774 | 10 |
PageRank | References | Authors |
1.08 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shou-hsuan Stephen Huang | 1 | 174 | 59.88 |
| C. K. Wong | 2 | 309 | 126.32 |