View article

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(|T₁|·|T₂·(deg(T₁) + deg(T₂))²), where |T₁| is the number of nodes in T₁ and deg(T₁) is the degree of T₁, i = 1.2. The algorithm is faster than the best known algorithm for tree edit when deg(T₁) and deg(T₂) are smaller than the depths of T₁ and T₂. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes MAX SNP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is MAX SNP-hard even if both trees have a bounded degree (Zhang and Jiang, 1994). Finally, multiple alignment of trees is discussed.