Node:Tree merging, Next:VLANs, Previous:Copying, Up:Top
We have two trees as parameters of entry which we have to merge. We never modify tese both trees. Technically, we begin by making another copy of the first tree. Then, we add the branches of the second tree not yet present in the first tree. At the end, we return this copy modified. We call this copy the new tree. However, if both trees don't have any common nodes or if we obtain a bucle, the working of fusion is left and we return a pointer NULL
We start the working of fusion by copying the first tree entried as parameter.
The second step consists in the research of the common node:
we make a traversing in depth of the first tree in order to define
the first node also present in the second tree.
tree1 tree2
E A
/ \ / \
/ \ / \
F C B I
/ \ / \
/ \ / \
K M H C
/ \
in this exemple, / \
the common node is "C". K L
After this work, we have to center the second tree on this common node:
by this way, this first common node becomes the root of the second work.
tree2 tree2 modified
A C
/ \ /|\
/ \ / | \
B I K L I
/ \ / \
/ \ / \
H C H A
/ \ |
/ \ |
K L B
By now, we are going to work only on this modified version of the second tree.
Then we begin by traversing the modified version of the second tree in depth. For each node met, we make the adapted processing.
If we meet a node "N" not present in the first tree,
we add this node to the new tree without forgetting to give
the name of the VLAN of this new branch.
In this goal, we research in the new tree the father "P" of this new node
in the second tree and add to this node "P" of the new tree a son named "N".
tree1 tree2 new tree
A P A
1/ \1 2/ \2 1/ \1
/ \ / \ / \
P C N L P C
1/ \1 2/ \ 1/ \1
/ \ / .. / \
E F N E F
If we meet a node "F" yet present in the first tree.
To begin, we verify that this node has the same first common ancestor
in the first tree as in the second.
We call first common ancestor of "F" the closest ancestor of "F" present
in both trees.
tree1 tree2
A C
/ \ / \
/ \ / \
B C W F
/ \ \
/ \ \
D E G
\
\
F In this exemple, the node "F"
has the same ancestor "C" in both trees.
If it's not the case, we stop the algorithm
because it involves that there is a buckle.
If the node studied has the same ancestor in both trees,
we distinguish tree cases.
In fact, when both trees had been built, some nodes can have been forgotten.
tree1 tree new tree
E P E
1/ \1 2/ \2 1/ \1
/ \ / \ / \
K P B F K P
\1 2/ \2 2/ \2,1
\ / \ / \
M H C B M
1/ \1 1/ \2,1
/ \ / \
L F L F
2/ \2
/ \
H C
This case squares with the fact that the father of this node "F"
in the second tree is a node present in the first tree:
the father of "F" in the second tree is the common ancestor.
In this case, we have to bring up to date the management of VLAN:
we have to add the name of the VLAN of the branch PF of the second tree
on the branches in the new tree which go from the node P to the node F
(ie the branches PH, HI and IF.
tree1 tree new tree
E P E
1/ \1 2/ \2 1/ \1
/ \ / \ / \ erase
K P B I K P |
\1 2/ \2 2/ | \ |
\ / \ /21| *F<-
F H F B I
1/ \1 2/ \2,1
/ \ / \
L G H F
/ \
/ \
L G
This case squares with the fact that the father I of this node F
in the second tree is not a node of the first tree.
The nodes H and I have yet been added to the first tree.
We have to erase F from son of P and its whole arborescence from the new tree.
Then we recopy this arborescence under I in the new tree.
We have also to bring up to date the value of VLANS of the branches
which go from the ancestor common P to the node studied F in the new tree.
In this goal, we add, to the list of VLANs of these branches,
the value of the branch PF (ie the branch "father of node studied -
node studied")in the first tree.
tree1 tree2 new tree
P P P P
| | | |
I J I J
| | | or |
F F J I
| |
F F
The problem is that we can't place the node I and J
because we don't know if I is the father of J or the contrary.
That's why we decide to choose arbitrarily to place firstly
the nodes of the second tree and after these of the first tree.
With this choose, we obtain the result:
tree1 tree2 new tree
P P E
1/ \1 2/ \2 1/ \1
/ \ / \ / \
K I B J K P
\1 2/ \2 2/ \1,2
\ / \ / \
F H F B J
1/ \1 2/\2,1
/ \ / \
L G H I
2,1|
|
F
1/ \1
/ \
L G
At the end of the algorithm,
we return the new tree which is the merge of both trees.