Optimal Binary Search Trees: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
=Overview= | =Overview= | ||
A [[Binary_Search_Trees#Balanced_Binary_Search_Trees|balanced binary search]] tree exposes all its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree might not be optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall. | A [[Binary_Search_Trees#Balanced_Binary_Search_Trees|balanced binary search]] tree exposes all its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree might not be optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall. An optimal search tree minimize the average search time with respect to a given set of probabilities over the keys. | ||
Revision as of 21:09, 2 November 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/GKCeN/problem-definition
- https://www.coursera.org/learn/algorithms-greedy/lecture/rUDLu/optimal-substructure
- https://www.coursera.org/learn/algorithms-greedy/lecture/0qjbs/proof-of-optimal-substructure
- https://www.coursera.org/learn/algorithms-greedy/lecture/3wrTN/a-dynamic-programming-algorithm-i
- https://www.coursera.org/learn/algorithms-greedy/lecture/5ERYG/a-dynamic-programming-algorithm-ii
Internal
Overview
A balanced binary search tree exposes all its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree might not be optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall. An optimal search tree minimize the average search time with respect to a given set of probabilities over the keys.