Name
Abstract | ||
|---|---|---|
Binary search trees with costs &agr; and &bgr;, respectively, on the left and right edges (lopsided search trees) are considered. The exact shape, minimum worst-case cost, and minimum average cost of lopsided trees of n internal nodes are determined for nonnegative &agr; and &bgr;; the costs are both roughly logp(n + 1) where p is the unique real number in the interval (1. 2] satisfying 1/p&agr; + 1/p&bgr; = 1. Search procedures are given that come within a small additive constant of the lower bounds. Almost-optimum algorithms for the lopsided case of unbounded searching are also obtained. Some extensions to nonconstant costs are briefly sketched. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1145/65950.65955 | J. ACM |
Keywords | DocType | Volume |
minimax recurrence relations,binary search,prefix-free codes,binary search trees,edge-weighted trees,search procedure,data structure,Almost-optimum algorithm,kraft's inequality,fibonacci trees,informa- tion theory,exact shape,minimum average cost,binary search tree,binary trees,coding theory,path lengths,n internal node,unbounded search. pereant qui ante nos nostra dixerunt! death to those who thought of our ideas before we did! -saint jerome: commentarius in ecclesiasten,additional key words and phrases: algorithmic analysis,minimum worst-case cost,lopsided case,optimum lopsided binary tree,lopsided tree,optimal trees,lopsided search tree,fibonacci numbers | Journal | 36 |
Issue | ISSN | Citations |
3 | 0004-5411 | 18 |
PageRank | References | Authors |
1.52 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjiv Kapoor | 1 | 18 | 1.52 |
| Edward M. Reingold | 2 | 2214 | 563.65 |