树堆 Treap

随机平衡的二叉搜索树：key 满足 BST、priority 满足最大堆。观察插入后节点如何按 priority 上浮旋转。

速度:

插入序列:

琥珀=当前节点，蓝色=本次旋转涉及的节点，p=priority（随机，越大越靠近根）

空树

初始化空 Treap（随机 priority 维持平衡）

步骤 1 / 18初始化

当前高亮行: 1(初始化)

1function insert(v) {

2 // 1. 按二叉搜索树规则插入，并赋予随机 priority

3 const x = bstInsert(v);

4 // 2. 若父节点 priority < 本节点，旋转上浮（维持最大堆）

5 while (parent(x) && priority(parent(x)) < priority(x))

6 rotate(x);

加载中…