Optimum Sequence Trees
Masahiro Miyakawa, Toshitsugu Yuba, Yoshio Sugito, Mamoru Hoshi · SIAM Journal on Computing · 1977
The construction problems of optimum sequence trees (or digital search trees) are considered in the following frameworks: 1. construction of optimum trees from a set of keys, 2. transformation of an arbitrary tree into an optimum one, 3. optimum insertions of keys into an optimum tree, 4. optimum deletions of keys from an optimum tree. Algorithms are shown. The number of operations needed for the algorithm in the framework 1 is at most $O(N^{2}L)$, and in the framework 2 it is at most $O(N^{3}L)$ both with $O(N)$ storage locations, where N and L are the number of keys and the length of coded keys respectively. Necessary and sufficient conditions for the optimality of sequence trees are also given.