Jump to navigation Jump to search
an optimal binary search tree (Optimal BST); sometimes called a weight-balanced
binary tree; is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.
|Complexity Classes||Algorithm Paper Links||Lower Bounds Paper Links|
|Polynomial > 3|