本文目录#

原理#

Treap = Tree + Heap。每个节点包含键值 key 与随机优先级 priority，满足：

  • 二叉搜索树性质：左子树 key < 节点 < 右子树；
  • 堆性质：父节点 priority < 子节点（最小堆）。

插入/删除使用旋转保证堆性质，从而实现期望平衡。

数据结构#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Treap {
    static class Node {
        int key, priority;
        Node left, right;
        int size;
        Node(int key, int priority) {
            this.key = key;
            this.priority = priority;
            this.size = 1;
        }
    }

    private final Random random = new Random();
    private Node root;

    private int size(Node node) { return node == null ? 0 : node.size; }
    private void update(Node node) { if (node != null) node.size = 1 + size(node.left) + size(node.right); }

    private Node rotateRight(Node y) {
        Node x = y.left;
        Node beta = x.right;
        x.right = y;
        y.left = beta;
        update(y); update(x);
        return x;
    }

    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node beta = y.left;
        y.left = x;
        x.right = beta;
        update(x); update(y);
        return y;
    }

    private Node insert(Node node, int key) {
        if (node == null) return new Node(key, random.nextInt());
        if (key < node.key) {
            node.left = insert(node.left, key);
            if (node.left.priority < node.priority) node = rotateRight(node);
        } else {
            node.right = insert(node.right, key);
            if (node.right.priority < node.priority) node = rotateLeft(node);
        }
        update(node);
        return node;
    }

    public void insert(int key) { root = insert(root, key); }

    public boolean contains(int key) {
        Node node = root;
        while (node != null) {
            if (key == node.key) return true;
            node = key < node.key ? node.left : node.right;
        }
        return false;
    }
}

应用场景#

  • 有序集合操作（插入、删除、秩统计）；
  • 动态区间问题（Treap + 延迟标记）；
  • 结合分裂/合并实现 Rope、可持久结构。

自检清单#

  • 是否使用随机优先级确保平衡？
  • 是否在操作后更新节点 size 等附加数据？
  • 是否根据需求扩展为可持久 Treap 或带懒标记 Treap？

参考资料#

本作品系原创，采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，转载请注明出处。