树的最小编辑距离

[francecil]

计算将一棵树 tree1 通过编辑，变为另一棵树 tree2 的最小编辑距离

操作定义如下：

• 删除节点，并将其子节点连接到父节点上，以保持有序。（前序遍历顺序不变）
• 在一个已知的节点，和这个节点的连续子节点的子序列之间插入一个节点。
• 更改这个节点的label

时间复杂度要求 O(n^3)

[francecil]

关键字：Tree Editing Distance

相关算法：

• Zhang and Shasha（1989年）：O(m²n²)
• Demaine et al.：O(n²m(1+log(m/n)))

相关论文：

• http://tree-edit-distance.dbresearch.uni-salzburg.at/#bibliography

相关代码：

• https://github.com/DatabaseGroup/tree-similarity