We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.
One way to merge these kind of trees is as follow (we denote by $E$ the empty binary tree) :
- merge ($E$, $B(l, x, r)$) = $B(l,x,r)$
- merge ($B(l, x, r)$, $E$) = $B(l,x,r)$
merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_1, B(l_2,x_2,r_2)$), $x_1, l_1$) when $x_1 \leq x_2$
merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_2, B(l_1,x_1,r_1)$), $x_2, l_2$) when $x_1 > x_2$
Thus when merging two binary trees we are exchanging the left and right subtrees. I am wondering why it's important to do so ?
I guess this is because we don't want our final binary tree to be pathological like for example a tree with only nodes on it's right (which will cause a big height). If this is the reason why we exchange the left and right subtrees when merging I am wondering what make us believe that with this merging function we will not encounter pathological trees ? I mean how can we be sure that this new merging function will not produce pathlogical binary trees ?
Also it's the first time I see a merging function that exchange the left and right subtree. So is this a common thing to do for some categories of binary trees like increasing trees ?
Thank you !