Treap

By the end, you can

• Explain what a treap is and name the two invariants it enforces simultaneously.
• Identify which node field each invariant constrains (key for BST, random priority for max-heap).
• Explain why random priorities yield expected O(log n) height via the shape-equivalence argument.
• Distinguish expected O(log n) from worst-case O(log n) and state which applies to treaps.
• Trace a treap insert: BST leaf placement followed by rotate-up steps until the heap invariant is restored.
• Describe split and merge, state their time complexities, and show how insert and delete reduce to them.
• Explain what an implicit treap is and what sequence operations it enables.