Merge two cartesian trees without rule keysA < keysB

Revision en1, by Jatana, 2018-01-06 17:32:30

I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
Node *l = NULL, *r = NULL;
int key, priority, cnt = 1;

Node *musorka = NULL;
}


and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
if (!node->musorka) return;
push(node->l);
push(node->r);

pair<Node*, Node*> spl = split(node->musorka, node->key);
pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);

if (spl2.first) {
node->cnt++;
}

node->l->musorka = spl.first;
node->r->musorka = spl2.second;
node->musorka = NULL;
}


then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Jatana 2018-01-06 17:32:30 982 Initial revision for English translation
ru2 Jatana 2018-01-06 17:17:09 25 Мелкая правка: '.second;\n}\n~~~~' -> '.second;\n node->musorka = NULL;\n}\n~~~~'
ru1 Jatana 2018-01-06 17:11:24 957 Первая редакция (опубликовано)