为什么说是上帝的骰子？ 解释这个问题，首先由这个数据结构的名字开始，Treap = Tree + Heap，即为树堆之意，然而实际上用到堆的地方就是利用了一个随机的值标记每个结点，然后根据这个值对树进行左旋、右旋操作来调整父子树直接的关系，你可以严格让它遵循小根堆也可以遵循大根堆，这都无所谓。 也就是说每个结点的结构需要额外存储一个随机值，来决定它是否旋转调整，这对比普通的BST就要优越很多了，但这个也看运气，如果骰子没摇好，出现极端的情况，则可能即便是旋转了多次还是效率低下，我后面对BST、Treap、AVL进行了各方面的对比。 相对AVL，它不需要记录深度，不需要根据深度来判断是否旋转，旋转这件事就完全交给老天了，而且也不存在复杂的旋转情况，只有左旋和右旋。 注意：我写的这个Treap是以大根堆的方式进行维护的！也就是父节点大于子节点的随机值。Treap实现1. 结点的结构struct node { //值、优先级(随机数、该数的总结点数、该结点的val次数 int val, priority, length, cnt; node *lchild; node *rchild; node() : val(0), length(1), cnt(1), lchild(nullptr), rchild(nullptr) { srand((unsigned) time(NULL));//记得重新设定种子 priority = rand(); } node(int val) : val(val), length(1), cnt(1), lchild(nullptr), rchild(nullptr) { srand((unsigned) time(NULL)); priority = rand(); } void update() { length = cnt; if (lchild != nullptr)length += lchild->length; if (rchild != nullptr)length += rchild->length; } }; 2. Treap的抽象数据结构class Treap { node *head; int length; public: /*construct&destruct*/ Treap() : head(nullptr), length(0) {} Treap(int val) : head(new node(val)), length(1) {} public://内部类设计迭代器 class iterator { node *head; node *root; public: /*迭代器部分*/ iterator(node *head, node *root) : head(head), root(root) {} iterator &operator++() { root = queryNext(head, root->val); return *this; } iterator operator++(int) { iterator t = *this; root = queryNext(head, root->val); return t; } iterator &operator--() { root = queryPre(head, root->val); return *this; } iterator operator--(int) { iterator t = *this; root = queryPre(head, root->val); return t; } int operator*() { return root->val; } bool operator!=(const iterator &t) { return t.root != root; } }; private: /*static function*/ /*rotate*/ static node *rotateLeft(node *root); static node *rotateRight(node *root); /*insert&remove*/ static node *insert(node *root, int val, int &size); static node *remove(node *root, int val, int &size); /*query rank&value*/ static int getLength(node *root); static int queryRank(node *root, int val);//快速查询val的排名 static…