Task: Text Categorization
Input (English): A prefix one of these is often used to store predictive dictionaries and can be implemented as a tagged union in ML. They are commonly used to sort keys for quick search lookup. One type of these allows in-order, pre-order, and post-order traversals. A balanced one has log entry-number worst-case runtime for insertion, deletion, and search; one always-balanced version is the red-black. This type of data structure consists of nodes that each have a unique parent node and link to some number of children nodes. For ten points, name these structures perhaps best known in their binary version, in which nodes are often called roots and leaves.
Output (English): Science