3 ms·
I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at mos
by nolemurs 10y ago
I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines.
Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
- Robin_Message 10y agoTree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N). Tree diff is harder because the range of operations is bigger. React.js cheats by insisting on keys for arrays so matching is much easier.