Approximate OBST

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