|
Garsia–Wachs Algorithm
The Garsia–Wachs algorithm is an efficient method for computers to construct optimal binary search trees and Huffman coding, alphabetic Huffman codes, in linearithmic time. It is named after Adriano Garsia and Michelle L. Wachs. Problem description The input to the problem, for an integer n, consists of a sequence of n+1 non-negative weights w_0,w_1,\dots, w_n. The output is a rooted binary tree with n internal nodes, each having exactly two children. Such a tree has exactly n+1 leaf nodes, which can be identified (in the order given by the binary tree) with the n+1 input weights. The goal of the problem is to find a tree, among all of the possible trees with n internal nodes, that minimizes the weighted sum of the ''external path lengths''. These path lengths are the numbers of steps from the root to each leaf. They are multiplied by the weight of the leaf and then summed to give the quality of the overall tree. This problem can be interpreted as a problem of constructing a binar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Optimal Binary Search Tree
In computer science, 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 value, expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic. In the static optimality problem, the tree cannot be modified after it has been constructed. In this case, there exists some particular layout of the nodes of the tree which provides the smallest expected search time for the given access probabilities. Various algorithms exist to construct or approximate the statically optimal tree given the information on the access probabilities of the elements. In the dynamic optimality problem, the tree can be modified at any time, typically by permitting tree rotations. The tree is considered to have a cursor starting at the root which it can move or use to perform modifications. In this c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |