Blog

Blog copied to clipboard

距离上一次写东西已经有3个月了，开学之后有点忙，而且又懒了。今天写的就算是对之前工作的内容的一部分做一些提取和精练。

什么是二叉树的差异识别

差异识别算法换句话说就是两棵二叉树的对比算法，本质上是求解一棵树演变为另一棵树的最短演变步骤。假如我们有两棵二叉树T_h（Host tree） 和 T_t（Target tree），那么差异识别算法要求解的就是T_h 如何通过最少的改动，哪些改动来变成T_t。

递归遍历方法的缺陷

一般情况下，对两棵二叉树进行比较使用的是递归遍历方式。如下图1所示，分别从T_h，T_t 的根结点开始，递归对比T_h，T_t 的每个子结点。设当前比较的结点分别为q_A，q_B，若发现q_A，q_B 非同一结点，则可马上断定T(q_A)，T(q_B) 整体（虚线框内）不相等。该算法复杂度为O(n)。

T(x)表示二叉树T中以x结点为根节点的子树，下同。

fg1.

该方法虽简洁高效，但其差异判断规则过于简陋。首先，对于某个结点是销毁还是移动，该算法无法判定，也就是无法复用结点。如图2，T_A 要演变为T_B，显然只需简单修改结点3的双亲结点，这时我们可以称结点3被“移动”了。然而在上述算法中，递归比较至结点1右孩子指针域时，会判定结点3被销毁。然后比较结点2右孩子指针域时，会判定需创建一个结点3。

fg2.

虽然能得到正确的结果，但是相比于单纯地移动结点3，该算法却增加了无必要的结点销毁和创建开销，若结点3包含复杂的信息，该开销对性能的影响会十分明显。这个问题产生的原因是在销毁某一结点时，算法无法得知接下来的步骤是否会再出现该结点。当然，可以修改算法使得在每次需要销毁结点前，都查找T_t 是否存在该结点，然而修改后的算法复杂度增加至O(n^2)。
其次，递归遍历算法根据结点判定子树相等情况是不合理的。在某些情况下，子树间虽不严格相等，但却高度相似。图3分别展示了T_h 中的子树T(2)，T_t 中的子树T(4)。T(2) 和T(4) 虽有不同的根结点（结点2和结点4），但其余结点均相等，因此我们可以称T(2) 相似于T(4)。

fg3.

这时，递归遍历算法比较得出T(2)，T(4) 不严格相等，因此在演变过程中，T_h 需要销毁整个T(2)，创建整个T(4)，这同样带来了极大的性能开销。此背后的原因是:

递归遍历算法是基于位置的比较，而不是基于结点本身的比较

线性差异识别

为了解决这两个问题，我们可以试着换一种思路，不进行递归遍历，而是将二叉树转化成线性结构进行对比，我称该方法为线性差异识别方法。该方法不基于递归遍历，而是将树形结构的T_h，T_t 转化为两个线性结构L_h，L_t，再对L_h，L_t 进行差异识别。其中，二叉树中的结点位于线性结构中的哪个位置都是无所谓的，不影响结果。
与遍历递归比较算法不同，线性差异识别算法基于结点本身的比较，而基于结点比较首先要保证参与对比的两个树形结构拥有相同的结点。而针对结点复用的问题，线性差异识别算法需要对L_h 建立一个额外的key-value哈希表node_table，其中L_h 的结点id作为key，结点本身作为value，使用哈希表也有一个很大的好处，就是提高结点访问速度。线性差异识别算法分成三个主要步骤，分别是扩展，修剪和对比。图4，5展示了如何根据T_h，T_t 建立L_h，L_t 和node_table，其中，为了使情况更复杂更具代表性，T_h，T_t 在图3基础上作了修改。

fg4.

fg5.

L_h，L_t 和node_table只保存结点的引用，而不是完整复制整个结点，保证了较低的性能开销。下面以图4，5的结构为例，演示线性差异识别算法的工作流程。其中n_h∈L_h 为L_h 中某一结点，n_t∈L_t 为L_h 中的某一结点。

Step1. 扩展

为了保证参与对比的两个树形结构拥有相同的结点，在得到L_h，L_t 后，我们需要根据L_t 对L_h 进行修改。扩展步骤主要任务是存在于L_t 而不存在于L_h 的结点添加到L_h 。首先，遍历L_t ，然后检查node_table是否存在与n_t 对应（即相同id）的n_h ，若存在，则将n_h 标记为已访问；若不存在，则将n_t 加入到L_h 和node_table，同时将n_t 标记为已访问。过程如图6所示。

fg6.

因为node_table的存在，使得在每次执行检查n_t 是否在L_h 有对应的结点n_h 这一操作时，复杂度从O(n) 降为O(1)。这时，L_h 被加入了新结点，因此该步骤被称为扩展。

Step2. 修剪

同样地，为了保证参与对比的两个结构拥有相同的结点，这一步根据扩展的结果，我们将于L_t 中不存在而于L_h 中存在的结点舍弃。对L_h 进行遍历，检查n_h 是否被标记为已访问，若发现n_h 未被访问过，则将n_h 从L_h 和node_table中移除。图7展示了该过程。

fg7.

至此，L_h与L_t皆拥有相同的结点。观察到此时L_h，L_t 的结点顺序并不相等，这对算法的正确性并无影响。

Step3. 对比

该步骤是线性差异识别算法的核心部分，该过程将L_h 与L_t 的对应结点进行对比，为了记录L_h，L_t 间的差异信息，我们使用一个差异队列diff_list，所有结点间的差异操作都保存到diff_list中。
上面分析递归遍历方法时我们已经知道了，单纯地进行相应结点间的位置得比较是没有意义的，在新旧树变化之间，单个结点的位置变化有多种可能，因此我们并不关心结点在树形结构中的位置，我们只需关心结点本身拥有的信息：

• 左孩子域
• 右孩子域
• 数据域

仅仅根据这3个信息，便能确定一棵二叉树。所以，对于两个对应的结点，只需对比这3个信息即可。图8描述了L_h，L_t 间需进行相互对比的对应的结点。
我们对L_t 进行遍历，在node_table中找到与n_t 对应的n_h。然后对比n_t 和n_h 间的信息:

左孩子域：

• 若n_t.lchild ≠ null且n_h.lchild = null，将Append_Child(n_h，n_t.lchild，LEFT)操作记录到diff_list
• 若n_t.lchild = null且n_h.lchild ≠ null，将Remove_Child(n_h，LEFT)操作记录到diff_list
• 若n_t.lchild ≠ null，n_h.lchild ≠ null且n_t.lchild ≠ n_h.lchild，将Remove_Child(n_h，LEFT)与Append_Child(n_h，n_t.lchild，LEFT)操作记录到diff_list

右孩子域：

• 若n_t.rchild ≠ null且n_h.rchild = null，将Append_Child(n_h，n_t.rchild，RIGHT)操作记录到diff_list
• 若n_t.rchild = null且n_h.rchild ≠ null，将Remove_Child(n_h，RIGHT)操作记录到diff_list
• 若n_t.rchild ≠ null，n_h.rchild ≠ null且n_t.lchild ≠ n_h.rchild将Remove_Child(n_h，RIGHT)与Append_Child(n_h，n_t.rchild，RIGHT)操作记录到diff_list

数据域：

• 若n_t.data ≠ n_h.data，将Alter_Data(n_h，n_t.data，n_h.data)操作记录到diff_list

当完成遍历时，diff_list中已记录了L_h，L_t 间的所有差异信息。可以发现，之所以L_h 和L_t 中结点顺序不一致并不影响算法的正确性，是因为查找n_h 是通过node_table而不是通过遍历L_h。

fg8.

差异识别的目标就是要得diff_list，之后T_h 可使用diff_list中的信息向T_h演变。要注意，差异识别过程并没有改变T_h 的结构，只是单纯地从T_h 和 T_t 间挖掘演化信息。

对于N叉树

说了这么多，然而这种方法只能用于对比二叉树，那么想要应用于N叉树可以吗？可以，当然可以，只不过要在Step3阶段做一些修改。二叉树比较简单，只有两个孩子结点域，对于N叉树，孩子结点域不确定，但是可以将N叉树结点的孩子结点域转化为数组，然后进行列表diff即可。换句话说就是：

在Step3阶段，将二叉树左右孩子结点域对比改为N叉树孩子域的列表diff。

--- EOF ---

获益良多

写的很好，循序渐进 👍👍

关于 「Step3 阶段」有推荐的资料嘛，这块始终没看明白 🤣