The Complexity of Trie Index Construction

True structures are a convenient way of indexing files in which a key consists of a number of attributes. Records correspond to leaves in the true. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trle for a file depends on the order in which attributes are tested. It is shown that determining minimal size tries is an NP-complete problem for several variants of tries and that, for tries m which leaf chains are deleted, determining the true for which average access time is minimal is also an NP-complete problem. These results hold even for files in which attribute values are chosen from a binary or ternary alphabet.