lundi 10 février 2020

Modified Treap expected height

I have usual treap, but with a slightly modified Merge operation. Normally merge contains lines like this:

if (ltree->priority > rtree->priority) {
    ltree->right = merge(ltree->right, rtree);
    return ltree;
} else {
    rtree->left = merge(ltree, rtree->left);
    return rtree;
}

So the modification is that we'll choose branch in if randomly, proportionally to subtree sizes, i.e. change if line to:

if (rand(1, ltree->size+rtree->size) <= ltree->size)

So the question is: how to prove that expected height for such a treap is O(log n)




Aucun commentaire:

Enregistrer un commentaire