继续treap代码

这是Treap的代码:

#include <bits/stdc++.h>

using namespace std;

struct Node {
  int key, priority;
  Node *left, *right;

  Node(int key, int priority) : key(key), priority(priority), left(NULL), right(NULL) {}
};

struct Treap {
  Node *root;

  Treap() : root(NULL) {}

  void rotateRight(Node *&p) {
    Node *q = p->left;
    p->left = q->right;
    q->right = p;
    p = q;
  }

  void rotateLeft(Node *&p) {
    Node *q = p->right;
    p->right = q->left;
    q->left = p;
    p = q;
  }

  void insert(Node *&p, int key, int priority) {
    if (p == NULL) {
      p = new Node(key, priority);
      return;
    }

    if (key < p->key) {
      insert(p->left, key, priority);
      if (p->priority < p->left->priority) {
        rotateRight(p);
      }
    } else {
      insert(p->right, key, priority);
      if (p->priority < p->right->priority) {
        rotateLeft(p);
      }
    }
  }

  void remove(Node *&p, int key) {
    if (p == NULL) {
      return;
    }

    if (key == p->key) {
      if (p->left == NULL || p->right == NULL) {
        Node *q = p;
        if (p->left == NULL) {
          p = p->right;
        } else {
          p = p->left;
        }
        delete q;
      } else {
        if (p->left->priority > p->right->priority) {
          rotateRight(p);
          remove(p->right, key);
        } else {
          rotateLeft(p);
          remove(p->left, key);
        }
      }
    } else if (key < p->key) {
      remove(p->left, key);
    } else {
      remove(p->right, key);
    }
  }

  bool search(Node *p, int key) {
    if (p == NULL) {
      return false;
    }
    if (key == p->key) {
      return true;
    }
    if (key < p->key) {
      return search(p->left, key);
    } else {
      return search(p->right, key);
    }
  }
};

int main() {
  Treap t;
  t.insert(t.root, 5, rand());
  t.insert(t.root, 3, rand());
  t.insert(t.root, 8, rand());
  t.insert(t.root, 1, rand());
  t.insert(t.root, 4, rand());
  t.insert(t.root, 6, rand());
  t.insert(t.root, 9, rand());