What are the complexities for treap operations? — For all the basic maintenance operations, they are O(log n) average case and O(n) worst case. - Search - Insert - Delete For these operations, O(m log n/m) for treaps of sizes m and n, with m ≤ n. - union - intersection - difference