Approximate OBST: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Approximate OBST (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The approximate optimal binary search tree problem is to construct a binary search tree on these $n$ keys, whose expected access time is within an approximation factor of the optimal time. == Related Problems == Generalizations: Optimal Binary Search T...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of elements | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 07:52, 10 April 2023
Description
Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The approximate optimal binary search tree problem is to construct a binary search tree on these $n$ keys, whose expected access time is within an approximation factor of the optimal time.
Related Problems
Generalizations: Optimal Binary Search Tree Problem
Related: Huffman Encoding, Alphabetic Tree Problem
Parameters
$n$: number of elements
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Melhorn's Approximation algorithm | 1975 | $O(n)$ | $O(n)$ | 0.63 H \leq P_opt \leq P_balanced \leq 2 + 1.44 H | Deterministic | Time & Space |
| Karpinski | 1996 | $O(n^{0.6})$ | $O({1})$ | \epsilon = o(1) | Parallel | Time |
| Larmore | 1987 | $O(n^{1.6})$ | $O(n)$ | \epsilon = o(1) | Deterministic | Time |
| Levcopoulos; Lingas; Sack | 1989 | $O(n)$ | $O(n)$ | $1 + \epsilon$ | Deterministic | Time |
| de Prisco | 1993 | $O(n)$ | $O(n)$ | Upper bound: $H + 1 - p_0 - p_n + p_{max}$ | Deterministic | Time |