Optimal Binary Search Trees (Q7361810)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Optimal_BST
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Optimal Binary Search Trees |
AFP entry Optimal_BST |
Statements
27 May 2018
0 references
Tobias Nipkow
0 references
Dániel Somogyi
0 references
Optimal Binary Search Trees (English)
0 references
This article formalizes recursive algorithms for the construction of optimal binary search trees given fixed access frequencies. We follow Knuth (1971), Yao (1980) and Mehlhorn (1984). The algorithms are memoized with the help of the AFP article Monadification, Memoization and Dynamic Programming , thus yielding dynamic programming algorithms.
0 references
