二叉树线性差异识别算法

[phenomLi]

距离上一次写东西已经有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](https://github.com/phenomLi/Blog/issues/24)即可。换句话说就是： > 在Step3阶段，将二叉树左右孩子结点域对比改为N叉树孩子域的列表diff。
--- EOF ---

[Ctrl-Ling]

获益良多

[ystarlongzi]

写的很好，循序渐进 👍👍

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