On a string, the operation of deletion, insertion, or substitution performed on a single symbol. On a tree, the deletion of a node v followed by the reassignment of all children of v to the node of which v was formerly a child, the insertion of a new node followed by the reassignment of some arcs departing from the parent of the new node, or the substitution of the label of one of the nodes with another label. Each edit operation may have an associated nonnegative real number representing its cost.