Problem description

  1. Here n refers to the number of VDOM nodes on the page, which is not very precise. And if we were to be a little bit more rigorous, we should assume that the number of nodes before the change is m, and the number of nodes after the change is n.

  2. React and Vue are optimized on the premise of “giving up the optimal solution”, which is essentially a trade-off with both advantages and disadvantages.

If this algorithm were used in other industries, such as medicine, it would not work. Why?

React and Vue make the following assumptions:

  • Detect VDOM changes that occur only in the same layer
  • Detecting VDOM changes depends on the key specified by the user

React and Vue do not detect changes that occur at different levels or when users of the same element specify different keys or when users of different elements specify the same key, causing unexplained problems.

However, React believes that the probability of the front end encountering the first situation is very small, and the second situation can be solved by prompting the user. Therefore, this trade-off is worthwhile. There is no sacrifice in spatial complexity, but in most cases there is a huge increase in time. Wise choice!

The basic concept

First of all, you have to get a basic idea.

In fact, this is a typical minimum editing distance problem. There are many related algorithms. For example, in Git, an object diff operation will be performed before submission, which is the minimum distance editing algorithm used.

Leetcode has the original title, and if you want to understand this O(n^3), you can look at this first.

We do the same with trees. We define three operations to convert one tree to another:

  • Delete Deletes a node and gives its children to its parent

  • Inserts a node into children

  • Modify Modifies the value of a node

In fact, there are many ways to go from one tree to another, and we want to find the least.

The intuitive way is to use dynamic programming to reduce time complexity through this mnemonic search.

algorithm

Since a tree is a recursive data structure, the simplest tree comparison algorithm is recursive processing.

This algorithm could be described in detail in a long paper, which is not covered here. There’s a copy of the code that you want to see and I hope it doesn’t scare you.

Specifically, the time complexity of the tree minimal distance editing algorithm is O(n^2m(1+logmn)), and we assume that m is equal to n, which becomes O(n^3).

digression

If you are interested in data structures and algorithms, you can pay attention to my [Leetcode problem solving](github.com/azl39798585…