Alphabetic Tree Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 38: Line 38:
[[File:Optimal Binary Search Trees - Alphabetic Tree Problem - Space.png|1000px]]
[[File:Optimal Binary Search Trees - Alphabetic Tree Problem - Space.png|1000px]]


== Space-Time Tradeoff Improvements ==  
== Time-Space Tradeoff ==  


[[File:Optimal Binary Search Trees - Alphabetic Tree Problem - Pareto Frontier.png|1000px]]
[[File:Optimal Binary Search Trees - Alphabetic Tree Problem - Pareto Frontier.png|1000px]]

Revision as of 14:44, 15 February 2023

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

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination