2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 23 at 17:23
  • $\begingroup$ 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. $\endgroup$ – greybeard Feb 23 at 17:38
  • $\begingroup$ It could be arbitrary, or you could be missing a part of the puzzle, which you are not telling us. $\endgroup$ – Yuval Filmus Feb 23 at 18:01
  • $\begingroup$ @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. $\endgroup$ – dzhqjk Feb 23 at 18:21
  • $\begingroup$ @Apass.Jack I've added some references to the post. I am hoping it makes evrything more clear. $\endgroup$ – dzhqjk Feb 23 at 18:22
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.