Lecture
Optimal Binary Search Tree
Description
This lecture covers the concept of optimal binary search trees, where a binary search tree is built from a sequence of distinct keys with probabilities for searches. The goal is to minimize the expected search cost, which is influenced by the depth of keys in the tree. The lecture explains the recursive formulation for calculating the expected search cost, the optimal substructure of building the tree, and the runtime analysis of the algorithm. Examples and pseudocode are provided to illustrate the concepts, along with discussions on graphs representation using adjacency matrices and lists.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.