# Merging of two increasing binary trees why do we exchange left and right subtree

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 !

Some references : Skew heap and min-heap

• Could you please edit the question to add a reference to the original place where "increasing" binary tree is defined? It is always very useful to include references. Among other benefits, a reference may determine whether there are other factors and how to adjust answer to your level of interest in the current case. Feb 23 '19 at 17:23
• I've seen such trees called min-heap (in its article about binary heap, English wikipedia claims a shape property (complete binary tree), too). I neither know nor see any condition or relation between left and right subtrees. I hold the occurrence of $r_1$ for the recursive merge and $l_1$ as the new right sub-tree to be pure happenstance. Feb 23 '19 at 17:38
• It could be arbitrary, or you could be missing a part of the puzzle, which you are not telling us. Feb 23 '19 at 18:01
• @YuvalFilmus I don't think this arbitrary, for example this way of merging binary trees is explained in the reference I've just added (skew heap) on the post. Feb 23 '19 at 18:21
• @Apass.Jack I've added some references to the post. I am hoping it makes evrything more clear. Feb 23 '19 at 18:22

One may ask whether amortization is really necessary in the analysis of skew heaps, or whether skew heaps are efficient in a worst-case sense. Indeed they are not: we can construct sequences of operations in which some operations take O(n) time. For example, suppose we insert $$n, n + 1, n - 1, n + 2, n - 2, n + 3, \dots , 1, 2n$$ into an initially empty heap and then perform delete min. The tree resulting from the insertions has a right path of $$n$$ nodes, and the delete min takes $$\Omega ( n)$$ time. (See Fig. 3.)