Construction of Optimal Binary Split Trees
Original Publication Date: 1984-Jan-01
Included in the Prior Art Database: 2005-Feb-02
Split trees are a new technique for storing records with skewed frequency distribution, where the conflicting functions of frequency ordering and subtree construction are decoupled. A polynomial time algorithm to construct optimal binary split trees is described below. The crucial idea in such trees is that two values are stored in each node, one of them being the key, the other being a split value. The split value is used as a guide for further search in the tree if the key value is not equal to the search value. Note that the record associated with the split value is not stored in the node but in one of its subtrees. Given a set of n keys k1, ..., kn and their access probabilities p(k1), ...