一、概念：随机平衡的二叉搜索树
Treap = Tree + heap。每个节点同时持有两个关键值：
key（或val）：满足二叉搜索树性质（左 < 根 < 右）。priority：随机生成，满足堆性质（父节点的 priority ≥ 子节点，即最大堆）。
BST 性质保证中序遍历有序；堆性质（靠随机 priority）让树在期望意义下平衡，从而插入 / 删除 / 查找期望 O(log n)。它不需要旋转平衡因子，实现比 AVL / 红黑树简单得多。
与 Splay 的区别：Splay 靠「访问即上移」获得摊还平衡；Treap 靠「随机 priority + 堆性质」获得期望平衡。
二、插入
- 按 BST 规则插入新节点，并赋予一个随机 priority。
- 若新节点的 priority 大于其父节点，则旋转（左旋或右旋）把新节点上浮一层；重复直到父节点的 priority ≥ 本节点（或新节点已到根）。
interface Node { val: number; pri: number; left: Node | null; right: Node | null; }
function rotateRight(y: Node): Node {
const x = y.left!;
y.left = x.right;
x.right = y;
return x;
}
function rotateLeft(x: Node): Node {
const y = x.right!;
x.right = y.left;
y.left = x;
return y;
}
function insert(root: Node | null, v: number): Node {
if (!root) return { val: v, pri: Math.random(), left: null, right: null };
if (v < root.val) {
root.left = insert(root.left, v);
if (root.left!.pri > root.pri) root = rotateRight(root);
} else if (v > root.val) {
root.right = insert(root.right, v);
if (root.right!.pri > root.pri) root = rotateLeft(root);
}
return root;
}