Optimal Binary Search Tree Problem

Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The optimal binary search tree problem is to construct a binary search tree on these $n$ keys that minimizes the expected access time.

Parameters

$n$ : number of elements

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Yao	1982	$O(n^2)$	$O(n^2)$
Knuth's DP algorithm	1971	$O(n^2)$	$O(n^2)$
DP algorithm (Gilbert, Moore)	1959	$O(n^3)$	$O(n^2)$
Naive algorithm	1940	$O(4^n/n^{3/2})$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms