Treap

pick a language to open the code

import random


class Node:
    def __init__(self, key):
        self.key = key
        self.priority = random.random()
        self.left = self.right = None


def rotate(node, to_right):
    pivot = node.left if to_right else node.right
    if to_right:
        node.left, pivot.right = pivot.right, node
    else:
        node.right, pivot.left = pivot.left, node
    return pivot


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
        if node.left.priority > node.priority:
            node = rotate(node, True)
    else:
        node.right = insert(node.right, key)
        if node.right.priority > node.priority:
            node = rotate(node, False)
    return node

function makeNode(key) {
  return { key, priority: Math.random(), left: null, right: null };
}

function rotate(node, toRight) {
  const pivot = toRight ? node.left : node.right;
  if (toRight) [node.left, pivot.right] = [pivot.right, node];
  else [node.right, pivot.left] = [pivot.left, node];
  return pivot;
}

function insert(node, key) {
  if (node === null) return makeNode(key);
  if (key < node.key) {
    node.left = insert(node.left, key);
    if (node.left.priority > node.priority) node = rotate(node, true);
  } else {
    node.right = insert(node.right, key);
    if (node.right.priority > node.priority) node = rotate(node, false);
  }
  return node;
}

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

static Node* rotate(Node* n, int to_right) {
    Node* pivot = to_right ? n->left : n->right;
    if (to_right) { n->left = pivot->right; pivot->right = n; }
    else { n->right = pivot->left; pivot->left = n; }
    return pivot;
}

Node* insert(Node* n, int key) {
    if (n == NULL) {
        Node* fresh = calloc(1, sizeof(Node));
        fresh->key = key;
        fresh->priority = rand();
        return fresh;
    }
    if (key < n->key) {
        n->left = insert(n->left, key);
        if (n->left->priority > n->priority) n = rotate(n, 1);
    } else {
        n->right = insert(n->right, key);
        if (n->right->priority > n->priority) n = rotate(n, 0);
    }
    return n;
}

struct Node {
    int key;
    int priority;
    Node* left = nullptr;
    Node* right = nullptr;
};

std::mt19937 priorities(std::random_device{}());

Node* rotate(Node* n, bool to_right) {
    Node* pivot = to_right ? n->left : n->right;
    if (to_right) { n->left = pivot->right; pivot->right = n; }
    else { n->right = pivot->left; pivot->left = n; }
    return pivot;
}

Node* insert(Node* n, int key) {
    if (n == nullptr) {
        Node* fresh = new Node{key};
        fresh->priority = static_cast<int>(priorities() >> 1);
        return fresh;
    }
    if (key < n->key) {
        n->left = insert(n->left, key);
        if (n->left->priority > n->priority) n = rotate(n, true);
    } else {
        n->right = insert(n->right, key);
        if (n->right->priority > n->priority) n = rotate(n, false);
    }
    return n;
}

class Node {
    public int Key;
    public int Priority;
    public Node Left, Right;
    public Node(int key, int priority) { Key = key; Priority = priority; }
}

static readonly Random Rng = new Random();

static Node Rotate(Node n, bool toRight) {
    Node pivot = toRight ? n.Left : n.Right;
    if (toRight) { n.Left = pivot.Right; pivot.Right = n; }
    else { n.Right = pivot.Left; pivot.Left = n; }
    return pivot;
}

static Node Insert(Node n, int key) {
    if (n == null) return new Node(key, Rng.Next());
    if (key < n.Key) {
        n.Left = Insert(n.Left, key);
        if (n.Left.Priority > n.Priority) n = Rotate(n, true);
    } else {
        n.Right = Insert(n.Right, key);
        if (n.Right.Priority > n.Priority) n = Rotate(n, false);
    }
    return n;
}

static class Node {
    int key, priority;
    Node left, right;

    Node(int key, int priority) { this.key = key; this.priority = priority; }
}

static final Random RNG = new Random();

static Node rotate(Node n, boolean toRight) {
    Node pivot = toRight ? n.left : n.right;
    if (toRight) { n.left = pivot.right; pivot.right = n; }
    else { n.right = pivot.left; pivot.left = n; }
    return pivot;
}

static Node insert(Node n, int key) {
    if (n == null) return new Node(key, RNG.nextInt());
    if (key < n.key) {
        n.left = insert(n.left, key);
        if (n.left.priority > n.priority) n = rotate(n, true);
    } else {
        n.right = insert(n.right, key);
        if (n.right.priority > n.priority) n = rotate(n, false);
    }
    return n;
}