Universal retrieval trees (Q1068838): Difference between revisions

A retrieval tree identifies members of a given set. The redundancy of a tree is defined to be the difference between the maximum length of a path in the tree and the binary logarithm of the cardinality of the set. Given a family \(\{A_{\theta}\}\) of sets, a retrieval tree is developed whose maximum redundancy over the family is minimum. The tree is used to make a biological key. The probabilistic variant of the problem is discussed.