# Alphabetic Tree Problem (Optimal Binary Search Trees)

Jump to navigation
Jump to search

## Description

A variant of the OBST problem is when only the gaps have nonzero access probabilities, and is called the optimal alphabetic tree problem.

## Related Problems

Generalizations: Optimal Binary Search Tree Problem

Related: Approximate OBST, Huffman Encoding

## Parameters

$n$: number of elements

## Table of Algorithms

Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|

Klawe; Mumey | 1993 | $O(n)$ | $O(n)$ | Exact | Deterministic | Time |

Garsia–Wachs algorithm | 1977 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | Time & Space |

Hu–Tucker algorithm | 1971 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | Time & Space |