Where does tree collide?

A tree is a finite set of nodes joined by edges so that one node is the root and every other node is reached from it by exactly one path, which means there are no cycles. Knuth sets it out this way in The Art of Computer Programming, where a tree is defined recursively: a root together with zero or more disjoint subtrees, each itself a tree. A binary tree is the special case in which every node has at most two children, a left and a right. The referent here is an abstract arrangement of data in memory, and what marks the construct is the structure itself, the parent-to-child links and the absence of cycles, not anything that grows or anything that happened in the past. It is a container that programs build, traverse, and reshape, and it differs from the biology meanings because nothing about it records descent or history.[1]

Unit

A rooted, acyclic arrangement of nodes

Recovery means

Not applicable

Measured by

Structural properties such as height, depth, and node count, checked by traversing the nodes

A phylogenetic tree is a branching diagram that shows how species are related by common ancestry, the tips standing for organisms and each branch point standing for a shared ancestor from which the lineages split. Baum, Smith, and Donovan describe in Science how to read one: the pattern of branching, not the left-to-right order of the tips, is the claim, and closeness on the page does not mean closeness of kin. The referent is the history of life itself, reconstructed from data, and the tree is a hypothesis about who descended from whom. It shares the shape and the vocabulary of roots and branches with the computer-science tree, but here the branching means a real evolutionary split that happened in time, a claim that can be right or wrong about the world rather than a container a program builds.[2]

Unit

A hypothesis about ancestry among lineages

Recovery means

Not applicable

Measured by

Branching topology inferred from molecular or morphological data, with branch support assessed statistically

A decision tree is a predictive model that sorts a case toward an outcome by asking a sequence of questions about its features, each internal node splitting the data on a threshold and each leaf giving a prediction. Breiman, Friedman, Olshen, and Stone set out the standard method in Classification and Regression Trees, growing the tree by choosing, at each node, the split that most reduces impurity, then pruning it back to avoid overfitting; Quinlan's Induction of decision trees develops a related information-gain criterion. The referent is a fitted rule learned from a training sample, and its purpose is to predict, so a decision tree can be evaluated for accuracy on new cases. It borrows the rooted, branching form of the computer-science tree, but it is a model estimated from data rather than a data structure, and unlike the phylogenetic tree its branches encode decision rules, not descent.[3][4]

Unit

A fitted predictive rule over feature space

Recovery means

Not applicable

Measured by

Predictive accuracy or error on held-out data, with tree size controlled by pruning