Merge two cartesian trees without rule keysA < keysB

Revision en1, by UnstoppableSolveMachine, 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?

Tags data structure, cartesian tree, innovations

History

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