平衡树是二叉查找树的优化,据说算法不稳定,本人猜测可能可以构造一种加入顺序,使之复杂度近似于 O(n2)O(n^2)O(n2),从而卡掉平衡树。事实上,本人见过一道题的数据一定程度上卡掉 Treap,使同一个用了 Treap 的代吗只有提交若干次才能 AC。请问如何出数据卡掉平衡树,或证明卡不掉平衡树,回答时请说明是那种平衡树。
Treap
AC