Optimal Binary Search Trees: Difference between revisions
| 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. An optimal search tree minimize the average search time with respect to a given set of probabilities over the keys. | 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. The cost of searching in the tree is given by the number of node assessments: if the key we look for is in the root, we only need to look at the root, so the number of node we need to assess is 1, if the key is immediately under the root, the cost is 2, and so on. | ||
Revision as of 21:14, 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. The cost of searching in the tree is given by the number of node assessments: if the key we look for is in the root, we only need to look at the root, so the number of node we need to assess is 1, if the key is immediately under the root, the cost is 2, and so on.