距离上一次写东西已经有3个月了，开学之后有点忙，而且又懒了。今天写的就算是对之前工作的内容的一部分做一些提取和精练。
什么是二叉树的差异识别
差异识别算法换句话说就是两棵二叉树的对比算法，本质上是求解一棵树演变为另一棵树的最短演变步骤。假如我们有两棵二叉树Th（Host tree） 和 Tt（Target tree），那么差异识别算法要求解的就是Th 如何通过最少的改动，哪些改动来变成Tt。
递归遍历方法的缺陷
一般情况下，对两棵二叉树进行比较使用的是递归遍历方式。如下图1所示，分别从Th，Tt 的根结点开始，递归对比Th，Tt 的每个子结点。设当前比较的结点分别为qA，qB，若发现qA，qB 非同一结点，则可马上断定T(qA)，T(qB) 整体（虚线框内）不相等。该算法复杂度为O(n)。
T(x)表示二叉树T中以x结点为根节点的子树，下同。
fg1.
该方法虽简洁高效，但其差异判断规则过于简陋。首先，对于某个结点是销毁还是移动，该算法无法判定，也就是无法复用结点。如图2，TA 要演变为TB，显然只需简单修改结点3的双亲结点，这时我们可以称结点3被“移动”了。然而在上述算法中，递归比较至结点1右孩子指针域时，会判定结点3被销毁。然后比较结点2右孩子指针域时，会判定需创建一个结点3。
fg2.
虽然能得到正确的结果，但是相比于单纯地移动结点3，该算法却增加了无必要的结点销毁和创建开销，若结点3包含复杂的信息，该开销对性能的影响会十分明显。这个问题产生的原因是在销毁某一结点时，算法无法得知接下来的步骤是否会再出现该结点。当然，可以修改算法使得在每次需要销毁结点前，都查找Tt 是否存在该结点，然而修改后的算法复杂度增加至O(n^2)。
其次，递归遍历算法根据结点判定子树相等情况是不合理的。在某些情况下，子树间虽不严格相等，但却高度相似。图3分别展示了Th 中的子树T(2)，Tt 中的子树T(4)。T(2) 和T(4) 虽有不同的根结点（结点2和结点4），但其余结点均相等，因此我们可以称T(2) 相似于T(4)。
fg3.
这时，递归遍历算法比较得出T(2)，T(4) 不严格相等，因此在演变过程中，Th 需要销毁整个T(2)，创建整个T(4)，这同样带来了极大的性能开销。此背后的原因是:
递归遍历算法是基于位置的比较，而不是基于结点本身的比较
线性差异识别
为了解决这两个问题，我们可以试着换一种思路，不进行递归遍历，而是将二叉树转化成线性结构进行对比，我称该方法为线性差异识别方法。该方法不基于递归遍历，而是将树形结构的Th，Tt 转化为两个线性结构Lh，Lt，再对Lh，Lt 进行差异识别。其中，二叉树中的结点位于线性结构中的哪个位置都是无所谓的，不影响结果。
与遍历递归比较算法不同，线性差异识别算法基于结点本身的比较，而基于结点比较首先要保证参与对比的两个树形结构拥有相同的结点。而针对结点复用的问题，线性差异识别算法需要对Lh 建立一个额外的key-value哈希表node_table，其中Lh 的结点id作为key，结点本身作为value，使用哈希表也有一个很大的好处，就是提高结点访问速度。线性差异识别算法分成三个主要步骤，分别是扩展，修剪和对比。图4，5展示了如何根据Th，Tt 建立Lh，Lt 和node_table，其中，为了使情况更复杂更具代表性，Th，Tt 在图3基础上作了修改。
fg4.
fg5.
Lh，Lt 和node_table只保存结点的引用，而不是完整复制整个结点，保证了较低的性能开销。下面以图4，5的结构为例，演示线性差异识别算法的工作流程。其中nh∈Lh 为Lh 中某一结点，nt∈Lt 为Lh 中的某一结点。
Step1. 扩展
为了保证参与对比的两个树形结构拥有相同的结点，在得到Lh，Lt 后，我们需要根据Lt 对Lh 进行修改。扩展步骤主要任务是存在于Lt 而不存在于Lh 的结点添加到Lh 。首先，遍历Lt ，然后检查node_table是否存在与nt 对应（即相同id）的nh ，若存在，则将nh 标记为已访问；若不存在，则将nt 加入到Lh 和node_table，同时将nt 标记为已访问。过程如图6所示。
fg6.
因为node_table的存在，使得在每次执行检查nt 是否在Lh 有对应的结点nh 这一操作时，复杂度从O(n) 降为O(1)。这时，Lh 被加入了新结点，因此该步骤被称为扩展。
Step2. 修剪
同样地，为了保证参与对比的两个结构拥有相同的结点，这一步根据扩展的结果，我们将于Lt 中不存在而于Lh 中存在的结点舍弃。对Lh 进行遍历，检查nh 是否被标记为已访问，若发现nh 未被访问过，则将nh 从Lh 和node_table中移除。图7展示了该过程。
fg7.
至此，Lh与Lt皆拥有相同的结点。观察到此时Lh，Lt 的结点顺序并不相等，这对算法的正确性并无影响。
Step3. 对比
该步骤是线性差异识别算法的核心部分，该过程将Lh 与Lt 的对应结点进行对比，为了记录Lh，Lt 间的差异信息，我们使用一个差异队列diff_list，所有结点间的差异操作都保存到diff_list中。
上面分析递归遍历方法时我们已经知道了，单纯地进行相应结点间的位置得比较是没有意义的，在新旧树变化之间，单个结点的位置变化有多种可能，因此我们并不关心结点在树形结构中的位置，我们只需关心结点本身拥有的信息：
仅仅根据这3个信息，便能确定一棵二叉树。所以，对于两个对应的结点，只需对比这3个信息即可。图8描述了Lh，Lt 间需进行相互对比的对应的结点。
我们对Lt 进行遍历，在node_table中找到与nt 对应的nh。然后对比nt 和nh 间的信息:
左孩子域：
- 若nt.lchild ≠ null且nh.lchild = null，将Append_Child(nh，nt.lchild，LEFT)操作记录到diff_list
- 若nt.lchild = null且nh.lchild ≠ null，将Remove_Child(nh，LEFT)操作记录到diff_list
- 若nt.lchild ≠ null，nh.lchild ≠ null且nt.lchild ≠ nh.lchild，将Remove_Child(nh，LEFT)与Append_Child(nh，nt.lchild，LEFT)操作记录到diff_list
右孩子域：
- 若nt.rchild ≠ null且nh.rchild = null，将Append_Child(nh，nt.rchild，RIGHT)操作记录到diff_list
- 若nt.rchild = null且nh.rchild ≠ null，将Remove_Child(nh，RIGHT)操作记录到diff_list
- 若nt.rchild ≠ null，nh.rchild ≠ null且nt.lchild ≠ nh.rchild将Remove_Child(nh，RIGHT)与Append_Child(nh，nt.rchild，RIGHT)操作记录到diff_list
数据域：
- 若nt.data ≠ nh.data，将Alter_Data(nh，nt.data，nh.data)操作记录到diff_list
当完成遍历时，diff_list中已记录了Lh，Lt 间的所有差异信息。可以发现，之所以Lh 和Lt 中结点顺序不一致并不影响算法的正确性，是因为查找nh 是通过node_table而不是通过遍历Lh。
fg8.
差异识别的目标就是要得diff_list，之后Th 可使用diff_list中的信息向Th演变。要注意，差异识别过程并没有改变Th 的结构，只是单纯地从Th 和 Tt 间挖掘演化信息。
对于N叉树
说了这么多，然而这种方法只能用于对比二叉树，那么想要应用于N叉树可以吗？可以，当然可以，只不过要在Step3阶段做一些修改。二叉树比较简单，只有两个孩子结点域，对于N叉树，孩子结点域不确定，但是可以将N叉树结点的孩子结点域转化为数组，然后进行列表diff即可。换句话说就是：
在Step3阶段，将二叉树左右孩子结点域对比改为N叉树孩子域的列表diff。
--- EOF ---
距离上一次写东西已经有3个月了，开学之后有点忙，而且又懒了。今天写的就算是对之前工作的内容的一部分做一些提取和精练。
什么是二叉树的差异识别
差异识别算法换句话说就是两棵二叉树的对比算法，本质上是求解一棵树演变为另一棵树的最短演变步骤。假如我们有两棵二叉树Th（Host tree） 和 Tt（Target tree），那么差异识别算法要求解的就是Th 如何通过最少的改动，哪些改动来变成Tt。
递归遍历方法的缺陷
一般情况下，对两棵二叉树进行比较使用的是递归遍历方式。如下图1所示，分别从Th，Tt 的根结点开始，递归对比Th，Tt 的每个子结点。设当前比较的结点分别为qA，qB，若发现qA，qB 非同一结点，则可马上断定T(qA)，T(qB) 整体（虚线框内）不相等。该算法复杂度为O(n)。
fg1.该方法虽简洁高效，但其差异判断规则过于简陋。首先，对于某个结点是销毁还是移动，该算法无法判定，也就是无法复用结点。如图2，TA 要演变为TB，显然只需简单修改结点3的双亲结点，这时我们可以称结点3被“移动”了。然而在上述算法中，递归比较至结点1右孩子指针域时，会判定结点3被销毁。然后比较结点2右孩子指针域时，会判定需创建一个结点3。
fg2.虽然能得到正确的结果，但是相比于单纯地移动结点3，该算法却增加了无必要的结点销毁和创建开销，若结点3包含复杂的信息，该开销对性能的影响会十分明显。这个问题产生的原因是在销毁某一结点时，算法无法得知接下来的步骤是否会再出现该结点。当然，可以修改算法使得在每次需要销毁结点前，都查找Tt 是否存在该结点，然而修改后的算法复杂度增加至O(n^2)。
其次，递归遍历算法根据结点判定子树相等情况是不合理的。在某些情况下，子树间虽不严格相等，但却高度相似。图3分别展示了Th 中的子树T(2)，Tt 中的子树T(4)。T(2) 和T(4) 虽有不同的根结点（结点2和结点4），但其余结点均相等，因此我们可以称T(2) 相似于T(4)。
fg3.这时，递归遍历算法比较得出T(2)，T(4) 不严格相等，因此在演变过程中，Th 需要销毁整个T(2)，创建整个T(4)，这同样带来了极大的性能开销。此背后的原因是:
线性差异识别
为了解决这两个问题，我们可以试着换一种思路，不进行递归遍历，而是将二叉树转化成线性结构进行对比，我称该方法为线性差异识别方法。该方法不基于递归遍历，而是将树形结构的Th，Tt 转化为两个线性结构Lh，Lt，再对Lh，Lt 进行差异识别。其中，二叉树中的结点位于线性结构中的哪个位置都是无所谓的，不影响结果。
与遍历递归比较算法不同，线性差异识别算法基于结点本身的比较，而基于结点比较首先要保证参与对比的两个树形结构拥有相同的结点。而针对结点复用的问题，线性差异识别算法需要对Lh 建立一个额外的key-value哈希表node_table，其中Lh 的结点id作为key，结点本身作为value，使用哈希表也有一个很大的好处，就是提高结点访问速度。线性差异识别算法分成三个主要步骤，分别是扩展，修剪和对比。图4，5展示了如何根据Th，Tt 建立Lh，Lt 和node_table，其中，为了使情况更复杂更具代表性，Th，Tt 在图3基础上作了修改。
fg4.
fg5.Lh，Lt 和node_table只保存结点的引用，而不是完整复制整个结点，保证了较低的性能开销。下面以图4，5的结构为例，演示线性差异识别算法的工作流程。其中nh∈Lh 为Lh 中某一结点，nt∈Lt 为Lh 中的某一结点。
Step1. 扩展
为了保证参与对比的两个树形结构拥有相同的结点，在得到Lh，Lt 后，我们需要根据Lt 对Lh 进行修改。扩展步骤主要任务是存在于Lt 而不存在于Lh 的结点添加到Lh 。首先，遍历Lt ，然后检查node_table是否存在与nt 对应（即相同id）的nh ，若存在，则将nh 标记为已访问；若不存在，则将nt 加入到Lh 和node_table，同时将nt 标记为已访问。过程如图6所示。
fg6.因为node_table的存在，使得在每次执行检查nt 是否在Lh 有对应的结点nh 这一操作时，复杂度从O(n) 降为O(1)。这时，Lh 被加入了新结点，因此该步骤被称为扩展。
Step2. 修剪
同样地，为了保证参与对比的两个结构拥有相同的结点，这一步根据扩展的结果，我们将于Lt 中不存在而于Lh 中存在的结点舍弃。对Lh 进行遍历，检查nh 是否被标记为已访问，若发现nh 未被访问过，则将nh 从Lh 和node_table中移除。图7展示了该过程。
fg7.至此，Lh与Lt皆拥有相同的结点。观察到此时Lh，Lt 的结点顺序并不相等，这对算法的正确性并无影响。
Step3. 对比
该步骤是线性差异识别算法的核心部分，该过程将Lh 与Lt 的对应结点进行对比，为了记录Lh，Lt 间的差异信息，我们使用一个差异队列diff_list，所有结点间的差异操作都保存到diff_list中。
上面分析递归遍历方法时我们已经知道了，单纯地进行相应结点间的位置得比较是没有意义的，在新旧树变化之间，单个结点的位置变化有多种可能，因此我们并不关心结点在树形结构中的位置，我们只需关心结点本身拥有的信息：
仅仅根据这3个信息，便能确定一棵二叉树。所以，对于两个对应的结点，只需对比这3个信息即可。图8描述了Lh，Lt 间需进行相互对比的对应的结点。
我们对Lt 进行遍历，在node_table中找到与nt 对应的nh。然后对比nt 和nh 间的信息:
左孩子域：
右孩子域：
数据域：
当完成遍历时，diff_list中已记录了Lh，Lt 间的所有差异信息。可以发现，之所以Lh 和Lt 中结点顺序不一致并不影响算法的正确性，是因为查找nh 是通过node_table而不是通过遍历Lh。
fg8.差异识别的目标就是要得diff_list，之后Th 可使用diff_list中的信息向Th演变。要注意，差异识别过程并没有改变Th 的结构，只是单纯地从Th 和 Tt 间挖掘演化信息。
对于N叉树
说了这么多，然而这种方法只能用于对比二叉树，那么想要应用于N叉树可以吗？可以，当然可以，只不过要在Step3阶段做一些修改。二叉树比较简单，只有两个孩子结点域，对于N叉树，孩子结点域不确定，但是可以将N叉树结点的孩子结点域转化为数组，然后进行列表diff即可。换句话说就是：
--- EOF ---