Optimal Binary Search Tree

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.

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.

Related lectures (20)

Related concepts (56)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Adjacency list

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges.

Binary search tree

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree. Binary search trees allow binary search for fast lookup, addition, and removal of data items.

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Random binary tree

In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution in which all distinct trees are equally likely. It is also possible to form other distributions, for instance by repeated splitting.

Intersection graph

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formally, an intersection graph G is an undirected graph formed from a family of sets by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is, Any undirected graph G may be represented as an intersection graph.

Graphs: Properties and Representations CS-119(h): Information, Computation, Communication

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Graphical Models: Representing Probabilistic Distributions PHYS-512: Statistical physics of computation

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Algorithms: Final Exam Review CS-250: Algorithms I

Provides a detailed review of the 2016 final exam, covering various algorithmic problems.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Statistical Analysis of Network Data MATH-448: Statistical analysis of network data

Introduces network data structures, models, and analysis techniques, emphasizing permutation invariance and Erdős-Rényi networks.