# 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 |