Approximate OBST

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.

Parameters

$n$ : number of elements

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


de Prisco	1993	$O(n)$	$O(n)$
Levcopoulos; Lingas; Sack	1989	$O(n)$	$O(n)$
Larmore	1987	$O(n^{1.6})$	$O(n)$
Melhorn's Approximation algorithm	1975	$O(n)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms