Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees)
Jump to navigation
Jump to search
Time Complexity
$O(n)$
Space Complexity
$O(n)$
(https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf, storing left/right subtrees' weights)
Description
Approximate?
Approximate
Approximation Factor: 0.63 H \leq P_opt \leq P_balanced \leq 2 + 1.44 H
Randomized?
No, deterministic
Model of Computation
Year
1975