随机化二叉搜索树（Treap）的原理与实现

1. 问题背景
二叉搜索树（BST）在理想情况下（平衡时）具有 O(log n) 的查询、插入、删除复杂度，但如果插入数据具有较强顺序性（例如升序插入），则会退化成链表，复杂度变为 O(n)。为了避免退化，常见方案是使用平衡二叉树（如 AVL 树、红黑树），但它们需要复杂的旋转操作来维护平衡条件。
随机化二叉搜索树（Treap）是一种简单而高效的数据结构，它通过引入随机优先级，以较大概率保持树的平衡，且实现比经典平衡树更简单。

2. Treap 的核心思想
Treap 是 Tree + Heap 的组合。每个节点包含两个属性：

1. key：遵循二叉搜索树的性质（左子树所有 key < 当前节点 key < 右子树所有 key）。
2. priority：一个随机分配的优先级，满足堆的性质（通常是最小堆或最大堆，以最小堆为例：父节点的 priority ≤ 子节点的 priority）。

通过随机分配 priority，并同时维护 BST 性质和堆性质，Treap 可以在期望上达到平衡，其期望高度为 O(log n)。

3. 数据结构定义
每个 Treap 节点可定义为：

struct TreapNode {
    int key;
    int priority;      // 随机值
    TreapNode* left;
    TreapNode* right;
    // 可附加其他信息，如子树大小、值等
};

通常我们使用最小堆性质（即父节点 priority 小于等于子节点 priority）。

4. 基本操作原理
4.1 旋转操作
为了维护堆性质，在插入或删除时可能破坏堆性质，需要通过旋转调整。旋转分为左旋和右旋，与 AVL 树旋转类似，但目的是让 priority 满足堆序。

• 右旋：当左子节点 priority 更小时，对当前节点右旋。
• 左旋：当右子节点 priority 更小时，对当前节点左旋。
  旋转后 BST 性质保持不变，但父子关系变化，可调整 priority 顺序。

4.2 插入操作
插入步骤：

1. 按照 BST 规则，递归找到 key 应插入的位置，创建新节点，并赋予一个随机 priority。
2. 从新节点向上回溯，检查堆性质是否满足（即当前节点 priority 是否小于父节点 priority）。
3. 如果不满足（例如当前节点 priority 比父节点小，但父节点 priority 应更小），则通过旋转将当前节点上移，直到堆性质满足。
   实际上，常用递归实现，插入到叶子后，通过旋转向上调整。

具体递归插入过程：

• 若当前节点为空，则新建节点返回。
• 若插入 key 小于当前节点 key，则插入左子树，插入完成后，如果左子节点 priority 小于当前节点 priority，则对当前节点右旋。
• 若插入 key 大于当前节点 key，则插入右子树，插入完成后，如果右子节点 priority 小于当前节点 priority，则对当前节点左旋。
• 旋转后，当前节点变为原来子节点的子节点，继续递归调整。

4.3 删除操作
删除步骤：

1. 找到要删除的节点。
2. 若该节点是叶子节点，直接删除。
3. 若该节点只有一个子节点，用子节点替代它。
4. 若有两个子节点，则比较左右子节点的 priority：
   • 若左子节点 priority 更小，则对该节点右旋（使左子节点上移），此时要删除的节点被转到右子树，递归地在右子树中删除该 key。
   • 若右子节点 priority 更小，则对该节点左旋，然后递归地在左子树中删除该 key。
     通过旋转，将被删除节点逐渐旋转到叶子或单子节点位置，然后删除。

5. 期望性能分析

• 随机 priority 相当于对插入顺序进行随机化，即使 key 有序，priority 的随机性也使得 Treap 的结构等价于随机顺序插入的 BST。
• 随机 BST 的期望高度为 O(log n)，因此 Treap 的查找、插入、删除期望时间复杂度均为 O(log n)。
• 最坏情况（极小概率下 priority 极度不平衡）高度为 O(n)，但概率极低。

6. 代码实现示例（C++）

#include <bits/stdc++.h>
using namespace std;

struct TreapNode {
    int key;
    int priority;
    TreapNode *left, *right;
    TreapNode(int k) : key(k), priority(rand()), left(nullptr), right(nullptr) {}
};

// 右旋
TreapNode* rightRotate(TreapNode* y) {
    TreapNode* x = y->left;
    TreapNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

// 左旋
TreapNode* leftRotate(TreapNode* x) {
    TreapNode* y = x->right;
    TreapNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    return y;
}

// 插入
TreapNode* insert(TreapNode* root, int key) {
    if (!root) return new TreapNode(key);
    if (key < root->key) {
        root->left = insert(root->left, key);
        if (root->left->priority < root->priority)
            root = rightRotate(root);
    } else {
        root->right = insert(root->right, key);
        if (root->right->priority < root->priority)
            root = leftRotate(root);
    }
    return root;
}

// 删除
TreapNode* deleteNode(TreapNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            TreapNode* temp = root->right;
            delete root;
            root = temp;
        } else if (!root->right) {
            TreapNode* temp = root->left;
            delete root;
            root = temp;
        } else {
            // 有两个子节点，将 priority 较小的子节点旋转上来
            if (root->left->priority < root->right->priority) {
                root = rightRotate(root);
                root->right = deleteNode(root->right, key);
            } else {
                root = leftRotate(root);
                root->left = deleteNode(root->left, key);
            }
        }
    }
    return root;
}

// 查找
bool search(TreapNode* root, int key) {
    if (!root) return false;
    if (root->key == key) return true;
    if (key < root->key) return search(root->left, key);
    return search(root->right, key);
}

7. 应用场景

• 需要动态维护有序集合，且希望实现简单、无需复杂平衡操作。
• 随机化数据结构适用于对最坏情况不敏感，但期望性能要求高的场景。
• 可扩展支持区间操作（通过维护子树大小实现 k-th 查询、split/merge 等），此时成为隐式Treap（又名笛卡尔树按索引作为 key）。

8. 总结
Treap 通过随机优先级保证了期望平衡，实现比 AVL/红黑树更简单，适合竞赛或快速原型开发。虽然存在理论上的最坏情况，但实际中几乎不会遇到。理解其“BST + 堆”的双重属性，以及旋转如何维护堆序，是掌握 Treap 的关键。