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

Question

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

Answer 1

Both leftist heaps and the skew heaps you consider here join two trees by "zipping" the trees along the rightmost path. Then left and right children are swapped to keep the left leaning property. In leftist heaps this in done where necessary, where in skew heaps left and right are always swapped. Hence the code.

You ask whether the skew heaps will never deteriorate into trees that have linear behaviour, instead of logarithmic. Well, this can happen.

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.)

Quoted from the original reference "self-adjusting heaps" by Sleator and Tarjan, SIAM Journal on Computing, which is linked on the wiki-page for skew heaps.