11. Treaps

views comments

Binary search tree (ordered dictionary) operations
Treaps: BST with respect to keys + min-heap with respect to priorities
Insert, delete, split, and join algorithms; time bounded by node depth
Theorem: Random priorities implies E[depth(v)] = O(log n) for every node v.
Lemma: i is a proper ancestor of k if and only if priority(i) = min{ priority(j) | i ≤ j ≤ k }
Lemma implies Theorem
Proof of Lemma
randomized quicksort again

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois