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