7 Algorithm to compare two trees, X and Y.
\r
9 A node x in X and node y in Y are defined to be
\r
10 similar iff the set of leaves in the subtree under
\r
11 x is identical to the set of leaves under y.
\r
13 A node is defined to be changed iff it is not
\r
14 similar to any node in the other tree.
\r
16 Nodes x and y are defined to be married iff every
\r
17 node in the subtree under x is similar to a node
\r
18 in the subtree under y. Married nodes are considered
\r
19 to be equal. The subtrees under two married nodes can
\r
20 at most differ by exchanges of left and right branches,
\r
21 which we do not consider to be significant here.
\r
23 A node is changed iff it is not married. If a node is
\r
24 changed, then it has a dissimilar node in its subtree,
\r
25 and it follows immediately from the definition of marriage
\r
26 that its parent is also a bachelor. Hence all nodes on the
\r
27 path from a changed node to the root are changed.
\r
29 We assume the trees have the same set of leaves, so
\r
30 every leaf is trivially both similar and married to
\r
31 the same leaf in the opposite tree. Changed nodes
\r
32 are therefore always internal (i.e., non-leaf) nodes.
\r
50 The following pairs of internal nodes are similar.
\r
57 Changed nodes in the first tree are i and j, changed nodes
\r
58 in the second tree are m and n.
\r
60 Node k and p are married, but i and m are not (because j
\r
61 and n are changed). The diffs are C, D and k.
\r
63 To achieve O(N) we avoid traversing a given subtree multiple
\r
64 times and also avoid comparing lists of leaves.
\r
66 We visit nodes in depth-first order (i.e., a node is visited
\r
69 If either child of a node is changed, we flag it as changed.
\r
71 If both children of the node we are visiting are married,
\r
72 we check whether the spouses of those children have the
\r
73 same parent in the other tree. If the parents are different,
\r
74 the current node is a bachelor. If they have the same parent,
\r
75 then the node we are visiting is the spouse of that parent.
\r
76 We assign this newly identified married couple a unique integer
\r
77 id. The id of a node is in one-to-one correspondence with the
\r
78 set of leaves in its subtree. Two nodes have the same set of
\r
79 leaves iff they have the same id. Changed nodes do not get
\r
83 void DiffTreesE(const Tree &NewTree, const Tree &OldTree,
\r
84 unsigned NewNodeIndexToOldNodeIndex[])
\r
87 Log("DiffTreesE NewTree:\n");
\r
94 if (!NewTree.IsRooted() || !OldTree.IsRooted())
\r
95 Quit("DiffTrees: requires rooted trees");
\r
97 const unsigned uNodeCount = NewTree.GetNodeCount();
\r
98 const unsigned uOldNodeCount = OldTree.GetNodeCount();
\r
99 const unsigned uLeafCount = NewTree.GetLeafCount();
\r
100 const unsigned uOldLeafCount = OldTree.GetLeafCount();
\r
101 if (uNodeCount != uOldNodeCount || uLeafCount != uOldLeafCount)
\r
102 Quit("DiffTreesE: different node counts");
\r
105 unsigned *IdToOldNodeIndex = new unsigned[uNodeCount];
\r
106 for (unsigned uOldNodeIndex = 0; uOldNodeIndex < uNodeCount; ++uOldNodeIndex)
\r
108 if (OldTree.IsLeaf(uOldNodeIndex))
\r
110 unsigned Id = OldTree.GetLeafId(uOldNodeIndex);
\r
111 IdToOldNodeIndex[Id] = uOldNodeIndex;
\r
115 // Initialize NewNodeIndexToOldNodeIndex[]
\r
116 // All internal nodes are marked as changed, but may be updated later.
\r
117 for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)
\r
119 if (NewTree.IsLeaf(uNewNodeIndex))
\r
121 unsigned uId = NewTree.GetLeafId(uNewNodeIndex);
\r
122 assert(uId < uLeafCount);
\r
124 unsigned uOldNodeIndex = IdToOldNodeIndex[uId];
\r
125 assert(uOldNodeIndex < uNodeCount);
\r
127 NewNodeIndexToOldNodeIndex[uNewNodeIndex] = uOldNodeIndex;
\r
130 NewNodeIndexToOldNodeIndex[uNewNodeIndex] = NODE_CHANGED;
\r
132 delete[] IdToOldNodeIndex;
\r
135 // Depth-first traversal of tree.
\r
136 // The order guarantees that a node is visited before
\r
137 // its parent is visited.
\r
138 for (unsigned uNewNodeIndex = NewTree.FirstDepthFirstNode();
\r
139 NULL_NEIGHBOR != uNewNodeIndex;
\r
140 uNewNodeIndex = NewTree.NextDepthFirstNode(uNewNodeIndex))
\r
142 if (NewTree.IsLeaf(uNewNodeIndex))
\r
145 // If either child is changed, flag this node as changed and continue.
\r
146 unsigned uNewLeft = NewTree.GetLeft(uNewNodeIndex);
\r
147 unsigned uOldLeft = NewNodeIndexToOldNodeIndex[uNewLeft];
\r
148 if (NODE_CHANGED == uOldLeft)
\r
150 NewNodeIndexToOldNodeIndex[uNewLeft] = NODE_CHANGED;
\r
154 unsigned uNewRight = NewTree.GetRight(uNewNodeIndex);
\r
155 unsigned uOldRight = NewNodeIndexToOldNodeIndex[uNewRight];
\r
156 if (NODE_CHANGED == NewNodeIndexToOldNodeIndex[uNewRight])
\r
158 NewNodeIndexToOldNodeIndex[uNewRight] = NODE_CHANGED;
\r
162 unsigned uOldParentLeft = OldTree.GetParent(uOldLeft);
\r
163 unsigned uOldParentRight = OldTree.GetParent(uOldRight);
\r
164 if (uOldParentLeft == uOldParentRight)
\r
165 NewNodeIndexToOldNodeIndex[uNewNodeIndex] = uOldParentLeft;
\r
167 NewNodeIndexToOldNodeIndex[uNewNodeIndex] = NODE_CHANGED;
\r
173 for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)
\r
175 Log(" [%3u]=", uNewNodeIndex);
\r
176 if (NODE_CHANGED == NewNodeIndexToOldNodeIndex[uNewNodeIndex])
\r
179 Log("%3u", NewNodeIndexToOldNodeIndex[uNewNodeIndex]);
\r
180 if ((uNewNodeIndex+1)%8 == 0)
\r
189 for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)
\r
191 unsigned uOld = NewNodeIndexToOldNodeIndex[uNewNodeIndex];
\r
192 if (NewTree.IsLeaf(uNewNodeIndex))
\r
194 if (uOld >= uNodeCount)
\r
196 Log("NewNode=%u uOld=%u > uNodeCount=%u\n",
\r
197 uNewNodeIndex, uOld, uNodeCount);
\r
198 Quit("Diff check failed");
\r
200 unsigned uIdNew = NewTree.GetLeafId(uNewNodeIndex);
\r
201 unsigned uIdOld = OldTree.GetLeafId(uOld);
\r
202 if (uIdNew != uIdOld)
\r
204 Log("NewNode=%u uOld=%u IdNew=%u IdOld=%u\n",
\r
205 uNewNodeIndex, uOld, uIdNew, uIdOld);
\r
206 Quit("Diff check failed");
\r
211 if (NODE_CHANGED == uOld)
\r
214 unsigned uNewLeft = NewTree.GetLeft(uNewNodeIndex);
\r
215 unsigned uNewRight = NewTree.GetRight(uNewNodeIndex);
\r
217 unsigned uOldLeft = OldTree.GetLeft(uOld);
\r
218 unsigned uOldRight = OldTree.GetRight(uOld);
\r
220 unsigned uNewLeftPartner = NewNodeIndexToOldNodeIndex[uNewLeft];
\r
221 unsigned uNewRightPartner = NewNodeIndexToOldNodeIndex[uNewRight];
\r
223 bool bSameNotRotated = (uNewLeftPartner == uOldLeft && uNewRightPartner == uOldRight);
\r
224 bool bSameRotated = (uNewLeftPartner == uOldRight && uNewRightPartner == uOldLeft);
\r
225 if (!bSameNotRotated && !bSameRotated)
\r
227 Log("NewNode=%u NewL=%u NewR=%u\n", uNewNodeIndex, uNewLeft, uNewRight);
\r
228 Log("OldNode=%u OldL=%u OldR=%u\n", uOld, uOldLeft, uOldRight);
\r
229 Log("NewLPartner=%u NewRPartner=%u\n", uNewLeftPartner, uNewRightPartner);
\r
230 Quit("Diff check failed");
\r