Approximate OBST (Optimal Binary Search Trees)
Jump to navigation
Jump to search
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 |