Approximate OBST (Optimal Binary Search Trees)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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