使用JS表示一棵树

略

对比两棵树的差异

属性对比

子节点对比

假设现在可以英文字母唯一地标识每一个子节点： 旧的节点顺序： a b c d e f g h i 现在对节点进行了删除、插入、移动的操作。新增j节点，删除e节点，移动h节点： 新的节点顺序： a b c h d f g i j 现在知道了新旧的顺序，求最小的插入、删除操作（移动可以看成是删除和插入操作的结合）。这个问题抽象出来其实是字符串的最小编辑距离问题（Edition Distance），最常见的解决算法是 Levenshtein Distance，通过动态规划求解，时间复杂度为 O(M * N)。但是我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定DOM操作，让算法时间复杂度达到线性的（O(max(M, N))。具体算法细节比较多，这里不累述，有兴趣可以参考代码。

看了2种描述操作的算法：
patch1对应：https://github.com/livoras/simple-virtual-dom/blob/master/lib/diff.js

目标对象在原对象指定位置对比：

  • 如果直接匹配，下一个
  • 如果删除原对象即可匹配则删除，否则插入
  • 删除多余的

patch2对应：https://github.com/Matt-Esch/virtual-dom/blob/master/vtree/diff.js

目标对象在原对象指定位置对比：

  • 如果直接匹配，下一个
  • 如果删除原对象即可匹配则删除，否则删除和插入都增加记录

示例：https://stackblitz.com/edit/react-ts-cxa9gv?file=App.tsx
5 4 2 3 1 => 3 2 1 5 4
patch1:

  • insert 3 to index 0 (354231)
  • insert 2 to index 1 (3254231)
  • insert 1 to index 3 (32154231)
  • remove index 7 (3215423)
  • remove index 6 (321542)
  • remove index 5 (32154)

patch2：

  • remove index 0 (4231)
  • remove index 0 (231)
  • remove index 1 (21)
  • insert 3 to index 0 (321)
  • insert 5 to index 3 (3215)
  • insert 4 to index 4 (32154)

1 4 2 3 5 => 5 4 2 3 1
patch1:

  • insert 5 to index 0 (514235)
  • remove index 1 (54235)
  • insert 1 to index 4 (542315)
  • remove index 5 (54231)

patch2：

  • remove index 0 (4235)
  • remove index 3 (423)
  • insert 5 to index 0 (5423)
  • inser 1 to index 4 (54231)

1 2 3 4 5 => 5 1 2 3 4
patch1:

  • insert 5 to index 0 (512345)
  • remove index 5 (51234)

patch2: