【AcWing 253. 普通平衡树 】 treap

题目链接
题意：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入数值 x。 删除数值 x(若有多个相同的数，应只删除一个)。 查询数值 x 的排名(若有多个相同的数，应输出最小的排名)。 查询排名为 x 的数值。 求数值 x 的前驱(前驱定义为小于 x 的最大的数)。 求数值 x 的后继(后继定义为大于 x 的最小的数)。 注意： 数据保证查询的结果一定存在。
分析：
现在先来介绍一下平衡树是什么吧，其实平衡树就是一棵二叉搜索树，对于学过数据结构的童鞋对这个二叉搜索树的概念应该并不陌生，他就是一棵二叉树，根节点的权值比左右孩子节点的权值都大，所以说这棵树要是完全二叉树的话，找一个节点的复杂度就是O(logn)，但是随着插入顺序的不同，二叉搜索树的形态也会不同，这棵树的形态在最极端的情况下就是一个长链，那么现在查询一个节点的时间复杂度就成了O(N)了，那么怎么优化呢，就

【AcWing 253. 普通平衡树 】 treap最先出现在Python成神之路。